https://leetcode-cn.com/problems/russian-doll-envelopes/
在看labuladong的算法书的时候，里面提到了这道信封嵌套问题。
当我们面对一个陌生的题目时，首先要想的就是如何将其转换成我们熟悉的问题。信封嵌套问题其实本质上就是一个二维的递增子序列问题。但是对二维的问题我并没有接触过，而一维的递增子序列我却很熟悉，之前已经做过两道了😀。于是便可以考虑是否将二维递增子序列问题进行降维，转换成我们熟悉的一维问题。
将二维数组进行排序，首先按宽度进行升序排序，当宽度相同时将对应的高度进行降序排序（确保不会出现将宽度相同的信封嵌套的情况）。于是便成功地进行了降维。
C++ STL里地sort算法，允许用户指定指定一个仿函数（functor）作为排序依据【源自STL源码剖析】。这里的代码利用地lambda表达式来对排序依据进行指定，也就是上面提到地排序规则。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int ans = 0, size = envelopes.size();
if(envelopes.empty()) return 0;
sort(envelopes.begin(), envelopes.end(), [](const vector<int>&a, const vector<int>&b){
return a[0]<b[0] || (a[0]==b[0] && a[1]>b[1]);
});
vector<int> dp(size,1);
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);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
这里的实现还可以利用二分法进一步优化。
