354. Russian Doll Envelopes

If we sort the envelopes by its width first, the problem becomes "Least Increasing Subsequences" which can be solved by dynamic programming.
Let dp[i] be the length of LIS until i.
So dp[i] = 1+dp[j] if envelope j can be fit into envelope i, where 0 <= j < i. Otherwise, dp[i] = 1.

1:  class Solution {  
2:  public:  
3:    int maxEnvelopes(vector<pair<int, int>>& envelopes) {  
4:      sort(envelopes.begin(), envelopes.end());  
5:      vector<int> dp(envelopes.size(), 1);  
6:      int ret = 0;  
7:      for (int i = 0; i < envelopes.size(); i++) {  
8:        for (int j = 0; j < i; j++) {  
9:          if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {  
10:            dp[i] = max(dp[j]+1, dp[i]);  
11:          }  
12:        }  
13:        ret = max(ret, dp[i]);  
14:      }  
15:      return ret;  
16:    }  
17:  };