C++刷LeetCode（646. 最长数对链）【动态规划】

糖逗

题目描述：

1. 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
   
2. 
   
3. 现在，我们定义一种跟随关系，当且仅当&#160;b < c&#160;时，数对(c, d)&#160;才可以跟在&#160;(a, b)&#160;后面。我们用这种形式来构造一个数对链。
   
4. 
   
5. 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
   
6. 
   
7. &#160;
   
8. 
   
9. 示例：
   
10. 
    
11. 输入：[[1,2], [2,3], [3,4]]
    
12. 输出：2
    
13. 解释：最长的数对链是 [1,2] -> [3,4]
    
14. &#160;
    
15. 
    
16. 提示：
    
17. 
    
18. 给出数对的个数在&#160;[1, 1000] 范围内。
    
19. 
    
20. 来源：力扣（LeetCode）
    
21. 链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
    
22. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int findLongestChain(vector<vector<int>>& pairs) {
   
4.         //排序
   
5.         sort(pairs.begin(), pairs.end(), [&](vector<int>&a, vector<int>&b){
   
6.             return a[1] < b[1];
   
7.         });
   
8.         //动态规划
   
9.         int len = pairs.size();
   
10.         vector<int>dp(len, 0);
    
11.         //初始值
    
12.         dp[0] = 1;
    
13.         for(int i = 1; i < len; i++){
    
14.             dp[i] = dp[i-1];
    
15.             int j = i - 1;
    
16.             while(j >= 0 && pairs[j][1] >= pairs[i][0])j--;
    
17.             if(j >= 0)dp[i] = max(dp[i], dp[j] + 1);
    
18.         }
    
19.         return dp[len-1];
    
20.     }
    
21. };

复制代码

参考链接：https://leetcode-cn.com/problems ... a-by-da-li-wang-35/