312. 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 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

链接： http://leetcode.com/problems/burst-balloons/

题解：

射气球游戏，射中气球以后得分是nums[i] * nums[i - 1] * nums[i - 2]，之后左右两边气球相连。这道题思路也很绕，看了dietpepsi的解答也很模糊，跟买卖股票with cooldown一样。方法应该是用dp或者divide and conquer，大概想法是每burst掉一个气球，我们做一遍2d dp。代码并不长，所以我把答案背下来了...擦。理解交给二刷了。

Time Complexity - O(n³)， Space Complexity - O(n²)

public class Solution {
    public int maxCoins(int[] orgNums) {
        if(orgNums == null || orgNums.length == 0) {
            return 0;
        }
        int len = orgNums.length + 2;
        int[] nums = new int[len];
        nums[0] = nums[len - 1] = 1;            // boundary
        for(int i = 0; i < orgNums.length; i++) {
            nums[i + 1] = orgNums[i];
        }
        int[][] dp = new int[len][len];
        
        for(int i = 1; i < len; i++) {          // first balloon
            for(int lo = 0; lo < len - i; lo++) {   // left part
                int hi = lo + i;                    // right part boundary
                for(int k = lo + 1; k < hi; k++) {      
                    dp[lo][hi] = Math.max(dp[lo][hi], nums[lo] * nums[k] * nums[hi] + dp[lo][k] + dp[k][hi]);
                }
            }  
        }
        
        return dp[0][len - 1];
    }
}

Reference:

https://leetcode.com/discuss/72216/share-some-analysis-and-explanations

https://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-32-ms-with-comments

https://leetcode.com/discuss/72215/java-dp-solution-with-detailed-explanation-o-n-3

https://leetcode.com/discuss/72683/my-c-code-dp-o-n-3-20ms

https://leetcode.com/discuss/73288/python-dp-n-3-solutions

https://leetcode.com/discuss/72802/share-my-both-dp-and-divide-conquer-solutions

https://leetcode.com/discuss/73924/my-36ms-c-solution