【LeetCode & 剑指offer刷题】动态规划与贪婪法题14：Burst Balloons

Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here leftand right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]Output: 167

Explanation: 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

C++

/*
问题：打气球游戏
方法：动态规划
dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币
dp[i][j] = max(dp[i][j], nums[i - 1]*nums[k]*nums[j + 1] + dp[i][k - 1] + dp[k + 1][j])， i ≤ k ≤ j
 遍历区间，遍历气球,在区间[i,j]中k气球最后打爆的情况，使最后能得到最多金币
 
我们其实只是更新了dp数组的右上三角区域，我们最终要返回的值存在dp[1][n]中，其中n是两端添加1之前数组nums的个数
 
例：
[3, 1, 5, 8]，得到的dp数组如下：
0    0    0    0    0    0
0    3    30   159  167  0
0    0    15   135  159  0
0    0    0     40    48   0
0    0    0     0      40   0
0    0    0     0      0    0
*/
class Solution
{
public:
    int maxCoins(vector<int>& nums)
    {
        if(nums.empty()) return 0;
           
        int n = nums.size();
        nums.insert(nums.begin(), 1); //首部填充0
        nums.push_back(1); //尾部填充0，首尾填充后，原nums中数的索引区间为[1,n]
        vector<vector<int>> dp(n+2, vector<int>(n+2)); //构建dp数组
       
        for (int len = 1; len <= n; len++) //区间长度（先算小区间，再算大区间，从小问题算到大问题）
        {
            for (int left = 1; left <= n - len + 1; left++) //左端点坐标,left =1~
            {
                int right = left + len - 1; //右端点坐标,right = len~n （在[1,n]范围left和right构成滑动窗）
                for (int k = left; k <= right; k++) //打爆的气球位置, k = left~right
                {
                    dp[left][right] = max(dp[left][right],
                    nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]);
//后面一项表示[left, right]区间中，k气球最后打爆的情况，故最后需要加上nums[left-1]*nums[k]*nums[right+1]项
                }
            }
        }
        return dp[1][n]; //dp[1][n]与 nums[0]和nums[n+1]关联，[1,n]区间对应原数组区间的数
    }
};