题目描述给你一个由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 rightleftright。现在我们定义一种 跟随 关系当且仅当b c b cbc时数对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 i1i1~n − 1 n-1n−1位置元素之后。但是在这道题目中对于以i ii位置元素为结尾的数对链i ii位置数对会接在0 00~i − 1 i-1i−1位置数对之后也会接在i 1 i1i1~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 1i1个数对是[ c , d ] [c, d][c,d]。如果[ a , b ] [a, b][a,b]要接在[ c , d ] [c, d][c,d]之后一定要满足d a d ada。但是已经排序了所以c a c aca数对内部是升序得到d c d cdc所以d c a d c adca得到d a d ada第i ii个数对肯定不会接在第i 1 i1i1个数对之后预处理完使用动态规划解决问题动态规划的思路和 最长递增子序列 类似状态表示一般根据经验 题目要求得到。经验就是以某一个位置为结尾题目要求是最长数对链的长度。所以d p [ i ] dp[i]dp[i]表示以i ii位置为结尾的所有数对链中最长数对链的长度状态转移方程以i ii位置为结尾的数对链可以分为长度 1 11和长度 1 11的长度 1 11时数对链只有一个数对d p [ i ] 1 dp[i] 1dp[i]1长度 1 11时以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-10ji−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(vectorvectorintpairs){sort(pairs.begin(),pairs.end(),[](vectorintv1,vectorintv2){returnv1[0]v2[0];});intnpairs.size();vectorintdp(n,1);intretdp[0];for(inti1;in;i){for(intji-1;j0;--j){if(pairs[i][0]pairs[j][1])dp[i]max(dp[j]1,dp[i]);}retmax(dp[i],ret);}returnret;}};
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 rightleftright。现在我们定义一种 跟随 关系当且仅当b c b cbc时数对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 i1i1~n − 1 n-1n−1位置元素之后。但是在这道题目中对于以i ii位置元素为结尾的数对链i ii位置数对会接在0 00~i − 1 i-1i−1位置数对之后也会接在i 1 i1i1~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 1i1个数对是[ c , d ] [c, d][c,d]。如果[ a , b ] [a, b][a,b]要接在[ c , d ] [c, d][c,d]之后一定要满足d a d ada。但是已经排序了所以c a c aca数对内部是升序得到d c d cdc所以d c a d c adca得到d a d ada第i ii个数对肯定不会接在第i 1 i1i1个数对之后预处理完使用动态规划解决问题动态规划的思路和 最长递增子序列 类似状态表示一般根据经验 题目要求得到。经验就是以某一个位置为结尾题目要求是最长数对链的长度。所以d p [ i ] dp[i]dp[i]表示以i ii位置为结尾的所有数对链中最长数对链的长度状态转移方程以i ii位置为结尾的数对链可以分为长度 1 11和长度 1 11的长度 1 11时数对链只有一个数对d p [ i ] 1 dp[i] 1dp[i]1长度 1 11时以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-10ji−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(vectorvectorintpairs){sort(pairs.begin(),pairs.end(),[](vectorintv1,vectorintv2){returnv1[0]v2[0];});intnpairs.size();vectorintdp(n,1);intretdp[0];for(inti1;in;i){for(intji-1;j0;--j){if(pairs[i][0]pairs[j][1])dp[i]max(dp[j]1,dp[i]);}retmax(dp[i],ret);}returnret;}};
