312. Burst Balloons - jiejackyzhang/leetcode-note GitHub Wiki

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.

Note:

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

Example:

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

解题思路为Dynamic Programming。

首先将nums[i]两端填上1，变成一个长度为n+2的新数组，balloons。 dp[left][right]表示以left，right为左右两端的数组的max coins。 若最后剩下的是balloons[i]（left<i<right），则：

dp[left][right] = max(balloons[left]*balloons[i]*balloons[right]+dp[left][i]+dp[i][right]) 

令k为sub problem的长度，则3 <= k <= n+2。则right = left + k - 1，以k为第一层循环，则当求后面的情形时，所需用的结果前面已经求出。

public class Solution {
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] balloons = new int[n+2];
        for(int i = 0; i < n; i++) balloons[i+1] = nums[i];
        balloons[0] = balloons[n+1] = 1;
        int[][] dp = new int[n+2][n+2];
        for(int k = 3; k <= n+2; k++) {
            for(int left = 0; left <= n+2-k; left++) {
                int right = left+k-1;
                for(int i = left+1; i < right; i++) {
                    dp[left][right] = Math.max(dp[left][right], balloons[left]*balloons[i]*balloons[right] + dp[left][i] + dp[i][right]); 
                }
            }
        }
        return dp[0][n+1];
    }
}
···