https://leetcode-cn.com/problems/russian-doll-envelopes/

????在看labuladong的算法書的時候，里面提到了這道信封嵌套問題。

????當(dāng)我們面對一個陌生的題目時，首先要想的就是如何將其轉(zhuǎn)換成我們熟悉的問題。信封嵌套問題其實本質(zhì)上就是一個二維的遞增子序列問題。但是對二維的問題我并沒有接觸過，而一維的遞增子序列我卻很熟悉，之前已經(jīng)做過兩道了??。于是便可以考慮是否將二維遞增子序列問題進行降維，轉(zhuǎn)換成我們熟悉的一維問題。

? ? 將二維數(shù)組進行排序，首先按寬度進行升序排序，當(dāng)寬度相同時將對應(yīng)的高度進行降序排序（確保不會出現(xiàn)將寬度相同的信封嵌套的情況）。于是便成功地進行了降維。

? ? C++ STL里地sort算法，允許用戶指定指定一個仿函數(shù)（functor）作為排序依據(jù)【源自STL源碼剖析】。這里的代碼利用地lambda表達式來對排序依據(jù)進行指定，也就是上面提到地排序規(guī)則。

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;

????}

};

這里的實現(xiàn)還可以利用二分法進一步優(yōu)化。