题解 | 信封嵌套

import sys

 # 22:51
 # 首先简化问题，将信封按照长或者宽从小到大排序
 # 那么考虑多少层嵌套，只需要考虑当前信封前，有多少信封的宽（或者长）小于当前信封，
 # 相当于找最长的递增子序列，假设dp[i]为以信封i为结尾的嵌套层数，
 # dp[i] = max(dp[0~i-1]中满足width 小于当前信封的dp[j] +1)

from collections import defaultdict

n = int(input())

letters = []

for _ in range(n):
    letter = list(map(int,input().split()))
    letters.append(letter)

letters.sort(key=lambda x: x[0])


dp = [0] * (n+1) # dp[i]为以i为最外层的信封嵌套数

letters = [[0,0]] + letters

for i in range(1,n+1):
    height,width = letters[i]
    for j in range(i):
        cur_height, cur_width = letters[j]
        # remove the situation where height the same but width less
        if cur_height<height and cur_width < width:
            dp[i] = max(dp[i],dp[j])
    dp[i] += 1

print(max(dp))