题目
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：
给出数对的个数在 [1, 1000] 范围内。
思路
动态规划或者贪心都可以做，贪心在这里比较容易。
贪心：需要将给定的数组按照第二个元素从小到大排序，从第一个最小的元素p开始算起，记录p[1]的值往后遍历，找到x[0] > p[1]即增长数链，更新p[1]的值为x[1]，循环往后即可。
动态规划：dp[i]代表到pairs[i]的最长数链长度，现将给定数组按照第二个元素排好序，（保证第一个元素只能做为数链首部），状态转移条件是：找到第i个元素之前符合条件的数取dp[i]和dp[j]+1的较大值作为dp[i]的值。记录数链长度的最大值即可。
题解
1、贪心
class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: pairs = sorted(pairs, key=lambda x:x[1]) ans, temp = 1, pairs[0][1] for i in range(1, len(pairs)): if pairs[i][0] > temp: ans += 1 temp = pairs[i][1] return ans
2、动态规划
class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: pairs = sorted(pairs, key=lambda x:x[1]) n = len(pairs) dp = [1] * n max_ = 1 for i in range(1, n): for j in range(i): if pairs[i][0] > pairs[j][1]: dp[i] = max(dp[i], dp[j] + 1) max_ = max(dp[i], max_) return max_
![[动态规划]Leetcode 1143.最长公共子序列（python）](https://ucc.alicdn.com/pic/developer-ecology/21ffe1475aca4887a57d95be29c5f7f5.png?x-oss-process=image/resize,h_160,m_lfit)
