354.Russian Doll Envelopes
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)
Example:Given envelopes = [[5,4],[6,4],[6,7],[2,3]]
, the maximum number of envelopes you can Russian doll is 3
([2,3] => [5,4] => [6,7]).
朴素解法，先对信封按width从小到大排序。
再观察height找出最长升序序列。
动态规划的方程为：
dp[i] = dp[k] + 1, while k < i and ith height is larger than kth height.
算法复杂度 O(n^2)
最快的应该是O(nlogn)，trick参考LIS算法
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
/**
* @brief
* dp[i] = dp[k] + 1, while k < i and i is larger than k
*/
class Solution {
public:
static bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first;
}
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
int N = envelopes.size();
vector<int> dp(N, 1);
int mx = (envelopes.size() == 0) ? 0 : 1;
sort(envelopes.begin(), envelopes.end(), cmp);
for(int i = 1, size = envelopes.size(); i < size; i++){
for(int j = 0; j < i; j++){
if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
dp[i] = max(dp[i], dp[j] + 1);
mx = max(mx, dp[i]);
}
}
}
return mx;
}
};
