题解 | #信封嵌套#
信封嵌套
https://www.nowcoder.com/practice/25fe1fc89c4c4e82bbc63df04bc6ca30
直接贴代码,本质上还是最长上升子序列的问题,如果自己写排序函数,应该可以进一步减少资源的占用。
def maxnums_envelope(a, n): dp = [1] * n maxnums = 1 for i in range(1, n): for j in range(i): if a[i][0] > a[j][0] and a[i][1] > a[j][1]: dp[i] = max(dp[i], dp[j] + 1) maxnums = max(dp[i], maxnums) return maxnums N = int(input()) arr = list() for i in range(N): arr.append(list(map(int, input().split()))) arr.sort() print(maxnums_envelope(arr, N))