LeetCode 312 Burst Balloons

标签: 动态规划问题 LeetCode 发布于:2022-02-19 21:23:19 编辑于:2022-02-19 23:38:43 浏览量:958

概述

https://leetcode.com/problems/burst-balloons/

Hard 哦。

动态规划法

选择:每次要戳哪一个气球。

状态:数组本身,可以用左右端点表示。

等等,戳破一个🎈后,数组就连起来了哦,也就是说子问题之间相互影响哦。

那状态不能用左右端点表示,那用序列化后的数组表示吧。不过每次序列化都要 O(n)?淦。

https://mp.weixin.qq.com/s/I0yo0XZamm-jMpG-_B3G8g

牛逼,换成开区间就不会相互影响了,我竟无言以对。

注意哦,不是选择戳破哪个气球,而是选择最后戳破哪个气球!

所以,最后这个气球其左右的值为 nums[i] 和 nums[j],而非 nums[k-1] 和 nums[k+1]

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> dp;
    int maxCoins(vector<int>& nums) {
        return helper(nums, -1, nums.size());
    }
    
    int helper(vector<int>& nums, int i, int j) {  // (i, j)
        if (j - i == 1) return 0;
        if (dp[i].count(j) != 0) {
            return dp[i][j];
        }
        int left = 1;
        if (i != -1) left = nums[i];
        int right = 1;
        if (j != nums.size()) right = nums[j];
        for (int t = i + 1; t <= j - 1; t ++) {
            dp[i][j] = max(dp[i][j], left * nums[t] * right + helper(nums, i, t) + helper(nums, t, j));
        }
        return dp[i][j];
    }
};

不过上面这个 TLE 了,离谱哦。

换成哈希表换成数组好了:

class Solution {
public:
    vector<vector<int>> dp;
    int maxCoins(vector<int>& nums) {
        dp.resize(nums.size()+2, vector<int>(nums.size()+2, -1));
        return helper(nums, -1, nums.size());
    }
    
    int helper(vector<int>& nums, int i, int j) {  // (i, j)
        if (j - i == 1) return 0;
        if (dp[i+1][j+1] != -1) return dp[i+1][j+1];
        int left = 1;
        if (i != -1) left = nums[i];
        int right = 1;
        if (j != nums.size()) right = nums[j];
        for (int t = i + 1; t <= j - 1; t ++) {
            dp[i+1][j+1] = max(dp[i+1][j+1], left * nums[t] * right + helper(nums, i, t) + helper(nums, t, j));
        }
        return dp[i+1][j+1];
    }
};

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