题目描述

你有一堆信封，并且已知它们的宽和长(w, h)。如果一个信封的长和宽都小于另一个信封，那就可以将这个信封放到那个信封中。

现在以俄罗斯套娃的方式将这些信封装起来，问最多可以装几层？

样例

给定信封：[[5,4],[6,4],[6,7],[2,3]]，
则最多可以套3层。
解释：[2,3] => [5,4] => [6,7]

算法

(动态规划) $O(n^2)$

先将所有信封按宽的长度从小到大排序，然后问题变成从左到右找一条最长的h严格单调递增的子序列，同时满足w也是严格单调递增的。
类似于最长上升序列问题，可以用动态规划解决。

状态表示：$f[i]$ 表示以第 $i$ 个信封为结尾的单调序列的最大长度。
状态转移：对于 $f[i]$，枚举 $j = 0 \sim i - 1$，如果第 $j$ 个信封的长和宽都小于第 $i$ 个信封，则用 $f[j] + 1$ 更新 $f[i]$。

时间复杂度分析：排序部分的时间复杂度是 $O(nlogn)$。动态规划部分一共有 $n$ 个状态，每个状态进行转移的计算量是 $O(n)$，所以动态规划的时间复杂度是 $O(n^2)$。总时间复杂度是 $O(n^2 + nlogn) = O(n^2)$。

C++ 代码

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end());
        int n = envelopes.size();
        vector<int> f(n);
        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second)
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        return res;
    }
};