646. 最长数对链
题目描述
给你一个由n nn个数对组成的数对数组p a i r s pairspairs，其中p a i r s [ i ] = [ l e f t , r i g h t ] pairs[i] = [left, right]pairs[i]=[left,right]且l e f t < r i g h t left < rightleft<right。
现在，我们定义一种 跟随 关系，当且仅当b < c b < cb<c时，数对p 2 = [ c , d ] p2 = [c, d]p2=[c,d]才可以跟在p 1 = [ a , b ] p1 = [a, b]p1=[a,b]后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：
输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。
示例 2：
输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
算法原理
之前做子序列问题的时候，以i ii位置元素为结尾的子序列，i ii位置元素一般都是接在0 00~i − 1 i-1i−1位置元素之后的，不会接在i + 1 i+1i+1~n − 1 n-1n−1位置元素之后。但是在这道题目中，对于以i ii位置元素为结尾的数对链，i ii位置数对会接在0 00~i − 1 i-1i−1位置数对之后，也会接在i + 1 i+1i+1~n − 1 n-1n−1位置数对之后。比如示例2 22，以1 11位置数对为结尾的子序列，1 11位置数对可能会接在0 00位置数对和2 22位置数对之后。所以要进行预处理
预处理的方法很简单，直接按照数对的第一个元素进行升序排序即可。假设排完序后，第i ii个数对是[ a , b ] [a, b][a,b]，第i + 1 i + 1i+1个数对是[ c , d ] [c, d][c,d]。如果[ a , b ] [a, b][a,b]要接在[ c , d ] [c, d][c,d]之后，一定要满足d < a d < ad<a。但是已经排序了，所以c > = a c >= ac>=a，数对内部是升序，得到d > c d > cd>c，所以d > c > = a d > c >= ad>c>=a，得到d > a d > ad>a，第i ii个数对肯定不会接在第i + 1 i+1i+1个数对之后
预处理完，使用动态规划解决问题，动态规划的思路和 最长递增子序列 类似
状态表示：一般根据经验+ ++题目要求得到。经验就是以某一个位置为结尾，题目要求是最长数对链的长度。所以d p [ i ] dp[i]dp[i]表示以i ii位置为结尾的所有数对链中，最长数对链的长度
状态转移方程：以i ii位置为结尾的数对链，可以分为长度= 1 = 1=1和长度> 1 > 1>1的
- 长度= 1 = 1=1时，数对链只有一个数对，d p [ i ] = 1 dp[i] = 1dp[i]=1
- 长度> 1 > 1>1时，以i ii位置为结尾的数对链可以看成以i − 1 , i − 2 , . . . , 0 i-1, i-2, ..., 0i−1,i−2,...,0位置结尾的数对链+ ++i ii位置数对。假设0 < = j < = i − 1 0 <= j <= i-10<=j<=i−1，以i − 1 , i − 2 , . . . , 0 i-1, i-2, ..., 0i−1,i−2,...,0位置结尾的数对链，它们分别最长的长度就是d p [ j ] dp[j]dp[j]，i ii位置数对要想跟在这些数对链之后，肯定要满足p a i r [ j ] [ 1 ] < p a i r [ i ] [ 0 ] pair[j][1] < pair[i][0]pair[j][1]<pair[i][0]，此时构成的新数对链的长度是d p [ j ] + 1 dp[j] + 1dp[j]+1。由于要最大值，所以d p [ i ] = m a x ( d p [ j ] + 1 , d p [ i ] ) dp[i] = max(dp[j] + 1, dp[i])dp[i]=max(dp[j]+1,dp[i])
初始化：以每一个位置为结尾的数对链，长度至少为1 11，所以初始化d p dpdp表为全1 11
填表顺序：从左到右
返回值：d p dpdp表中元素的最大值
代码
classSolution{public:intfindLongestChain(vector<vector<int>>&pairs){sort(pairs.begin(),pairs.end(),[](vector<int>&v1,vector<int>&v2){returnv1[0]<v2[0];});intn=pairs.size();vector<int>dp(n,1);intret=dp[0];for(inti=1;i<n;++i){for(intj=i-1;j>=0;--j){if(pairs[i][0]>pairs[j][1])dp[i]=max(dp[j]+1,dp[i]);}ret=max(dp[i],ret);}returnret;}};