题解 | #信封嵌套问题# 自己给做出来了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
       /*
        二维问题是信封嵌套，一维问题就是一个数组中最长递增子序列是多少。
        如何将二维问题转化成一维问题呢？
        信封=长X宽。
        1，先对长进行递增排序，若长相等的，宽度要递减排序
        所以从后遍历，若宽度>前面的，表示后面可以嵌套前面的。
*/
    static bool cmp(vector<int> &a, vector<int> &b) {
        if (a[0] == b[0]) {
            return a[1] > b[1];
        }
        return a[0] < b[0];
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        // 对输入进行判断
        if(letters.size() == 0) {
            return 0;
        }
        int len = letters.size();
        sort(letters.begin(), letters.end(), cmp);
        vector<int>dp(len, 1);
        int ret = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (letters[i][1] > letters[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                ret = max (ret, dp[i]);
            }
        }
        return ret;
    }
};