Burst Balloons(Medium)打气球游戏

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 left and 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.

注意：

• 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

例子：

Given [3, 1, 5, 8]

Return 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

解题思路：DP

State:dp[i][j]: the number of max coins can collect between i and j.

For a position x in [i,j], where to burst it? So this goes into a divide and conquer method

Burst at x, track the sum, and record the max into dp[i][j]

我们维护一个二维动态数组dp，其中dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币。题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样我们可以在原数组两边各填充一个1，这样方便于计算。这道题的最难点就是找递归式，如下所示：

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 )

Init: create dp[n+2][n+2]. (from 0 to n+1)

Return: dp[1][n]

 public int maxCoins(int[] iNums) {
    int n = iNums.length;
    int[] nums = new int[n + 2];
    for (int i = 0; i < n; i++)
        nums[i + 1] = iNums[i];

    nums[0] = nums[n + 1] = 1;
    int[][] dp = new int[n + 2][n + 2];

    for (int len = 1; len <= n; len++) {
        for (int left = 1; left <= n - len + 1; left++) {
            int right = left + len - 1;
            for (int x = left; x <= right; x++) {
                dp[left][right] = Math.max(dp[left][right], dp[left][x - 1] +
                        nums[left - 1] * nums[x] * nums[right + 1] + dp[x + 1][right]);
            }
        }
    }
    return dp[1][n];
}