题解 | #几步可以从头跳到尾# 刘二东

class Solution { /* 1，将二维问题降道一维，最长递增子序列。 计算能有多少个信封组成俄罗斯套娃=计算宽度数组中最长递增子序列。

2，按照宽度递增排序，高度数组中最大递增子序列的长度就是能有多少个信封组成俄罗斯套娃。

3，宽度不同时，按照增序排列，宽度相同时，按照递减排列，防止[6,4]、[6,7]这样的排序。

https://blog.csdn.net/Gaozihang777/article/details/118095661 */

public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ static bool cmp(const vector A, const vector B) { if (A[0] == B[0]) { return A[1] > B[1]; } else { return A[0] < B[0]; } }

int maxLetters(vector<vector<int> >& letters) {
    int len = letters.size();
    if (len == 0 || len == 1) {
        return len;
    }
    sort(letters.begin(), letters.end(), cmp);
    vector<int> dp(len, 1);
    int maxCnt = 1;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < i; j++) {
            if (letters[i][1] > letters[j][1]) {
                dp[i] = max (dp[j] + 1, dp[i]);
                maxCnt = max(maxCnt, dp[i]);
            }
        }
    }

    return maxCnt;
}

};