tag:
- Hard;
- DP;
question:
??You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Note: Rotation is not allowed.
Example:
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
思路：
??本題給了我們一堆大小不一的信封浓镜，讓我們像套俄羅斯娃娃那樣把這些信封都給套起來，容易想到用 DP 劲厌，這是一種 brute force 的解法膛薛，首先要給所有的信封按從小到大排序，首先根據(jù)寬度從小到大排补鼻，如果寬度相同哄啄，那么高度小的再前面，這里用 STL 里面的 sort 风范，然后開始遍歷咨跌，對于每一個信封，我們都遍歷其前面所有的信封硼婿，如果當前信封的長和寬都比前面那個信封的大锌半，那么我們更新dp數(shù)組，代碼如下：
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty() || envelopes[0].empty()) return 0;
sort(envelopes.begin(), envelopes.end(), comparator);
int res = 0, n = envelopes.size();
vector<int> dp(n, 1);
for (int i=0; i<n; ++i) {
for (int j=0; j<i; ++j) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1])
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
static bool comparator(vector<int> a, vector<int> b) {
if (a[0] == b[0])
return a[1] < b[1];
else
return a[0] < b[0];
}
};
