题解 | #信封嵌套问题# 你知道为什么要x轴升序，y轴降序吗

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    /*
    将问题降维为最长递增子序列问题。
    */
    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
        // 做输入判断
        // 按照长度递增排序，宽度按递减排序
        // dp(i)表示i可以嵌套多少信封，所以j应该是<i
          int len = letters.size();
        if (len == 0 || len == 1) {
            return len;
        }
        sort(letters.begin(), letters.end(), cmp);
        vector<int>dp(letters.size(), 1);
        int cnt = 1;
        for (int i = 0; i < letters.size(); i++) {
            for (int j = 0; j < i; j++) {
                if(letters[i][1] > letters[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);   
                    cnt = max(cnt, dp[i]);
                                     
                }
            }
        }
        return cnt;
    }
};