312. Burst Balloons

Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen becomes adjacent.

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

Note:
(1) You may imaginenums[-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]

Return167

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

Solution:

1. num[ ] represents an copy of nums with num[0] = 1 and num[len+1] = 1
2. dp[i][j] represents the maximum number we can get from i to j
3. for every x(i < x <j), put x as the last balloon within the range from i to j to burst, dp[left][right] = max(dp[i][j], num[x] * num[left] * num[right] + dp[left][x] + dp[x][right])
4. update the dp array fromstep = 2 to dp_lengthbetween left and right

public class Solution {
    public int maxCoins(int[] nums) {
       if(nums == null || nums.length == 0){
           return 0;
       }

       int len = nums.length;
       int[] num = new int[len+2];
       for(int i = 0; i < len; i++){
           num[i+1] = nums[i];
       }
       num[len+1] = 1;
       num[0] = 1;

       int[][] dp = new int[len+2][len+2];

       for(int k = 2; k < len+2; k++){
           for(int left = 0; left < len+2 -k; left++){
                int right = left + k;
                for(int i = left + 1; i < right; i++){
                    dp[left][right] = Math.max(dp[left][right], num[left] * num[i] * num[right] + dp[left][i] + dp[i][right]);
                }
           }
       }
       return dp[0][len+1];
    }
}

5.Time: O($$N^3$$)

6.Reference:
https://discuss.leetcode.com/topic/30746/share-some-analysis-and-explanations
http://bookshadow.com/weblog/2015/11/30/leetcode-burst-balloons/