LeetCode 354 Russian Doll Envelopes

Tag: 动态规划问题 Posted on 2022-02-15 16:47:52 Edited on 2022-02-15 18:09:08 Views: 185

概述

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

极值问题,无脑动态规划

动态规划法(O(n^2) 时间复杂度)

  1. base case:
  2. 状态:
  3. 选择:要不要
  4. dp 函数 / 数组的定义:dp[i][j] = 信封最小要能容纳长 i 宽 j 的情况下的最大装填数量

代码:

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> dp;
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int ans = 0;
        for (const auto& e : envelopes) {
            ans = max(ans, helper(envelopes, e[0], e[1]));
        }
        return ans;
    }
    
    int helper(vector<vector<int>>& envelopes, int w, int h) {
        if (dp[w][h] != 0) return dp[w][h];
        int cnt = 0;
        for (const auto& e : envelopes) {
            if (e[0] > w && e[1] > h) cnt = max(cnt, helper(envelopes, e[0], e[1]));
        }
        cnt ++;
        dp[w][h] = cnt;
        return cnt;
    }
};

O(n^2) 的时间复杂度,TLE 了。

排下序,早停一下:

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> dp;
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int ans = 0;
        sort(envelopes.rbegin(), envelopes.rend());
        for (const auto& e : envelopes) {
            ans = max(ans, helper(envelopes, e[0], e[1]));
        }
        return ans;
    }
    
    int helper(vector<vector<int>>& envelopes, int w, int h) {
        if (dp[w][h] != 0) return dp[w][h];
        int cnt = 0;
        for (const auto& e : envelopes) {
            if (e[0] <= w) break;
            if (e[0] > w && e[1] > h) cnt = max(cnt, helper(envelopes, e[0], e[1]));
        }
        cnt ++;
        dp[w][h] = cnt;
        return cnt;
    }
};

还是 TLE,过分了啊喂。

动态规划法(转换为最长递增子序列问题)

https://labuladong.gitee.io/algo/3/24/80/#二解法

先按宽度升序排序,如果宽度相同则按高度降序排序(目的是避免选中相同宽度的下一个值), 这样我们就将问题转换为一个最长递增子序列的问题:

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

O(n^2) 的时间复杂度,依旧超时。 这里要注意,由于 i = envelopes.size() - 2,所以 ans 要初始化为 1,否则遇到只有一个信封的就挂了。

只能上二分搜索用那个 O(nlogn) 的解法了。

搜索的是最左的哦。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>&b) -> bool {
            if (a[0] == b[0]) return a[1] > b[1];
            else return a[0] < b[0];
        });
        
        vector<int> top;
        
        for (int i = 0; i < envelopes.size(); i ++) {
            int l = 0, r = top.size();
            while (l < r) {
                int m = (l + r) / 2;
                if (top[m] >= envelopes[i][1]) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            if (l == top.size()) {
                top.push_back(envelopes[i][1]);
            } else {
                top[l] = envelopes[i][1];
            }
        }
        
        return top.size();
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/