LeetCode 312. 戳气球

发表于 | 分类于 |
字数统计: 482 | 阅读时长 ≈ 2

题面：https://leetcode-cn.com/problems/burst-balloons/

题意

有$n$个气球，编号为$0$到$n-1$，每个气球上都标有一个数字，这些数字存在数组$nums$中。

现在要求你戳破所有的气球。
每当你戳破一个气球$i$时，你可以获得$ nums[left] \times nums[i] \times nums[right]$ 个硬币。 这里的$left$和$right$代表和$i$相邻的两个气球的序号。注意当你戳破了气球$i$后，气球$left$和气球$right$就变成了相邻的气球。
求所能获得硬币的最大数量。

解法

肯定是dp了。
而且是一个区间dp。令$dp[i][j]$表示戳破$i+1, i+2, …, j - 1$个气球
设$k$是$i$到$j$中最后一个被戳破的气球，则有

然后区间长度从小到大转移即可。

代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int len = nums.size();
        int dp[len + 10][len + 10] = {};
        vector<int> a(len + 10);
        a[0] = a[len + 1] = 1;
        for(int i = 0; i < len; i++)
            a[i + 1] = nums[i];
        for(int l = 2; l <= len + 1; l++)
            for(int i = 0, j = i + l; j <= len + 1; i++, j++)
                for(int k = i + 1; k < j; k++)
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
        
        return dp[0][len + 1];
    }
};

记忆化写法

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
class Solution {
public:
    vector<vector<int>> dp;
    int maxCoins(vector<int>& nums) {
        vector<int> a = {1};
        for(int i: nums) {
            a.push_back(i);
        }
        a.push_back(1);
        int siz = a.size();
        dp.resize(siz);
        for (auto& idx: dp) {
            idx.resize(siz);
        }
        return getMax(0, nums.size() + 1, a);
    }
    int getMax(int l, int r, vector<int>& a) {
        if (l == r || r == l + 1) {
            return 0;
        }
        if (dp[l][r]) {
            return dp[l][r];
        }
        int ret = 0;
        for (int k = l + 1; k < r; k++) {
            ret = max(ret, a[k] * a[l] * a[r] + getMax(l, k, a) + getMax(k, r, a));
        }
        dp[l][r] = ret;
        return ret;
    }
};