leetcode 354. Russian Doll Envelopes

排序 + 动态规划

class Solution {
    
public:static bool cmp(const vector<int>& a, const vector<int>& b) {
    if (a[0] == b[0])   return a[1] > b[1];return a[0] < b[0];}int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), cmp);int size = envelopes.size();int dp[size + 1];for (int i = 0; i <= size; i ++)    dp[i] = 1;int res = 0;for (int i = 0; i < envelopes.size(); i ++) {
    for (int j = 0; j < i; j ++) {
    if (envelopes[i][1] > envelopes[j][1]) dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}return res;}
};