经典算法题型之俄罗斯套娃信封问题（二）

解题思路

简要概括题意，求一组二维上升子序列 p1,p2,...,pm ，同时满足：

由此我们将本问题转化成了基础的 LIS 问题，具体代码如下所示。

C++ 代码实现

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