动态规划（二维最长递增子序列问题）
- 将一维问题简单扩展到二维，即
两维同时升序（18�at，约1400ms）
代码语言：javascript
复制class Solution {
public:
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 maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), cmp);
int size = envelopes.size();
vector<int> dp(size 1, 1);
int len = 0;
for (int i = 0; i < size; i ) {
for (int j = 0; j < i; j )
if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1])
dp[i] = max(dp[i], dp[j] 1);
len = max(len, dp[i]);
}
return len;
}
- 将一维问题巧妙扩展到二维，即
第一维升序，第二维降序，仅按第二维进行标准最长递增子序列解决（54�at，约1000ms）
代码语言：javascript
复制class Solution {
public:
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 maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), cmp);
int size = envelopes.size();
vector<int> dp(size 1, 1);
int len = 0;
for (int i = 0; i < size; i ) {
for (int j = 0; j < i; j )
if (envelopes[j][1] < envelopes[i][1])
dp[i] = max(dp[i], dp[j] 1);
len = max(len, dp[i]);
}
return len;
}
};
