LeetCode 312 Burst Balloons

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

概述

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];
    }
};

Links: leetcode-312-burst-balloons