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

一刷
题解：

我们用数组dp[lo][hi]表示从i到j的子串能够构成的最大解
i表示子串长度，k表示在字串内the last one to burst, k in [lo, hi]，则有表达式：
dp[lo][hi] = ballons[lo-1]ballons[k]ballons[hi+1]+ dp[lo][k-1] + dp[k+1][hi])
并保存k从lo遍历到hi时候的最大值。

public class Solution {
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length + 2;
        int[] ballons = new int[len];
        ballons[0] = ballons[len-1] = 1;//boundary
        for(int i=0; i<nums.length; i++){
            ballons[i+1] = nums[i];
        }
        
        int[][] dp = new int[len][len];
        for(int i=1; i<len-1; i++){//the number of ballon to blust
            for(int lo = 1; lo<= len - i - 1; lo++){//hi - lo = i
                int hi = lo - 1 + i;
                for(int k = lo; k<=hi; k++)//lo<k<=hi, k is the last one to blust
                    dp[lo][hi] = Math.max(dp[lo][hi], ballons[lo-1]*ballons[k]*ballons[hi+1]+ dp[lo][k-1] + dp[k+1][hi]);
            }
        }
        
        return dp[1][len-2];//the answer locates in the range of [1, len-2]
    }
}