646.最长数对链（动态规划）

解题思路：
动态规划（最长升序子序列变体）
dp[i]表示到索引为i的这个元素为止，有多少个满足要求的数对，即第一个元素大于前一个元素的第二个元素。
动态转移方程

if(pairs[i][0]>pairs[j][1]){
    
                    dp[i]=max(dp[i],dp[j]+1);

但是由于给的数组是无序的，因此需要首先对数组作处理。

首先数组按照第二个元素的升序排列，而不是按第一个元素的升序排列，原因是前者能够为后面留下更多的空间。

sort(pairs.begin(),pairs.end(),
            [](const vector<int>& a,const vector<int>& b)
            {
    
                return a[1]<b[1];
            });

完整代码如下

class Solution {
    
public:
    int findLongestChain(vector<vector<int>>& pairs) {
    
        int n=pairs.size();
        if(n==1) return 1;
        sort(pairs.begin(),pairs.end(),
            [](const vector<int>& a,const vector<int>& b)
            {
    
                return a[1]<b[1];
            });
        vector<int> dp(n,1);
        int max_len=0;
        for(int i=0;i<n;++i){
    
            for(int j=0;j<i;++j){
    
                if(pairs[i][0]>pairs[j][1]){
    
                    dp[i]=max(dp[i],dp[j]+1);
                }
                max_len=max(max_len,dp[i]);
            }
        }

        return max_len;
    }
};