leetcode-354-线性DP-俄罗斯套娃信封问题

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 动态规划，O（n^2），可用二分查找优化
class Solution {
public:
    struct compare{
        // 排序，w升序，w相同时，h降序
        // 两个宽度相同的信封不能相互包含，逆序排序保证在 w 相同的数对中最多只选取一个
        bool operator()(vector<int> &a, vector<int> &b){
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        }
    };

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if(envelopes.empty()) return 0;
        
        sort(envelopes.begin(), envelopes.end(), compare());

        // 最长上升子序列问题
        int n = envelopes.size();
        vector<int> dp(n, 1);
        int res = 1;

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < i; ++j){
                if(envelopes[j][1] < envelopes[i][1]) 
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            res = max(res, dp[i]);
        }

        return res;
    }
};