LeetCode 312. 戳气球(C++) 动态规划

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

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
1
2
3
4
5

示例 2：

输入：nums = [1,5]
输出：10
1
2

提示：

n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100

动态规划

例题：

给定四个球分别为[3,1,5,8],其实可以看做数组[1,3,1,5,8,1];

解题思路：

我们令dp[start][end]表示从start到end之间的气球戳破之后能得到的最大值
则本题就是求解dp[0][5],即戳破3,1,5,8四个气球能得到的最大值。

为了求解dp[0][5],我们要先得到递推公式
我们假设最后戳破的是第i个气球，则得到的值为
dp[0][5]=dp[0][i]+dp[i][5]+nums[0]*nums[i]*nums[5];
**即求得递推公式 **
dp[start][end]=max(dp[start][i]+dp[i][end]+nums[start]*nums[i]*nums[end])
初始化dp数组为：

其中0开始0结尾的气球序列的值一定为0,0开始1结尾的气球序列的值也为0（补齐边界之后，两个元素的数组的求值为0）.
依次类推可以填出所有的0值。
0开始2结束的值即为戳破气球1的值 dp[0][2]=nums[0]*nums[1]*nums[2]+dp[0][1]+dp[1][2]
依次推出表格里其余的值。

最后返回dp[0][5]即为所求的值。

作者：lidada
链接：https://leetcode-cn.com/problems/burst-balloons/solution/chuo-qi-qiu-dong-tai-gui-hua-wen-ti-by-lidada/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();//数组长度
        //二维向量 （n+2）*(n+2)
        vector<vector<int>> rec(n + 2, vector<int>(n + 2));
        vector<int> val(n + 2);
        val[0] = val[n + 1] = 1; //补齐边界
       //重新摆放数组元素位置
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
        //i从n-1左移到0，j从i+2右移到n+1
            for (int j = i + 2; j <= n + 1; j++) {
			//i相当于start;j相当于end；
			//k表示最后一个删除的元素,k在i+1到j-1之间右移

                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];// 
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = max(rec[i][j], sum);
                }
            }
        }
        return rec[0][n + 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