676_最长数对链.org

题目

思路

和最长上升子序列思想一致

状态 dp[i] 表示以 i 结尾所能形成的最长上升子序列的长度。因为可以以任何顺序选择其中的一些数对来构造，所以先对 pairs 排序

code

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:

        pairs = sorted(pairs, key=lambda x: (x[0], -x[1]))
        n = len(pairs)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
        # print(dp)
        return dp[-1]