LeetCode 354 Russian Doll Envelopes
概述
https://leetcode.com/problems/russian-doll-envelopes/
极值问题，无脑动态规划
动态规划法（O(n^2) 时间复杂度）
- base case：
- 状态：
- 选择：要不要
- dp 函数 / 数组的定义：dp[i][j] = 信封最小要能容纳长 i 宽 j 的情况下的最大装填数量
代码：
class Solution {
public:
unordered_map<int, unordered_map<int, int>> dp;
int maxEnvelopes(vector<vector<int>>& envelopes) {
int ans = 0;
for (const auto& e : envelopes) {
ans = max(ans, helper(envelopes, e[0], e[1]));
}
return ans;
}
int helper(vector<vector<int>>& envelopes, int w, int h) {
if (dp[w][h] != 0) return dp[w][h];
int cnt = 0;
for (const auto& e : envelopes) {
if (e[0] > w && e[1] > h) cnt = max(cnt, helper(envelopes, e[0], e[1]));
}
cnt ++;
dp[w][h] = cnt;
return cnt;
}
};
O(n^2) 的时间复杂度，TLE 了。
排下序，早停一下：
class Solution {
public:
unordered_map<int, unordered_map<int, int>> dp;
int maxEnvelopes(vector<vector<int>>& envelopes) {
int ans = 0;
sort(envelopes.rbegin(), envelopes.rend());
for (const auto& e : envelopes) {
ans = max(ans, helper(envelopes, e[0], e[1]));
}
return ans;
}
int helper(vector<vector<int>>& envelopes, int w, int h) {
if (dp[w][h] != 0) return dp[w][h];
int cnt = 0;
for (const auto& e : envelopes) {
if (e[0] <= w) break;
if (e[0] > w && e[1] > h) cnt = max(cnt, helper(envelopes, e[0], e[1]));
}
cnt ++;
dp[w][h] = cnt;
return cnt;
}
};
还是 TLE，过分了啊喂。
动态规划法（转换为最长递增子序列问题）
https://labuladong.gitee.io/algo/3/24/80/#二解法
先按宽度升序排序，如果宽度相同则按高度降序排序（目的是避免选中相同宽度的下一个值）， 这样我们就将问题转换为一个最长递增子序列的问题：
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>&b) -> bool {
if (a[0] == b[0]) return a[1] > b[1];
else return a[0] < b[0];
});
int ans = 1;
vector<int> dp(envelopes.size(), 1);
for (int i = envelopes.size() - 2; i >= 0; i --) {
for (int j = i + 1; j < envelopes.size(); j ++) {
if (envelopes[i][1] < envelopes[j][1]) {
dp[i] = max(dp[i], 1 + dp[j]);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
O(n^2) 的时间复杂度，依旧超时。
这里要注意，由于 i = envelopes.size() - 2，所以 ans 要初始化为 1，否则遇到只有一个信封的就挂了。
只能上二分搜索用那个 O(nlogn) 的解法了。
搜索的是最左的哦。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>&b) -> bool {
if (a[0] == b[0]) return a[1] > b[1];
else return a[0] < b[0];
});
vector<int> top;
for (int i = 0; i < envelopes.size(); i ++) {
int l = 0, r = top.size();
while (l < r) {
int m = (l + r) / 2;
if (top[m] >= envelopes[i][1]) {
r = m;
} else {
l = m + 1;
}
}
if (l == top.size()) {
top.push_back(envelopes[i][1]);
} else {
top[l] = envelopes[i][1];
}
}
return top.size();
}
};