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. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find themaximumcoins you can collect by bursting the balloons wisely.

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

Have you met this question in a real interview?

Yes

Example

Given[4, 1, 5, 10]
Return270

nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20
nums = [4, 5, 10]    burst 5, get coins 4 * 5 * 10 = 200 
nums = [4, 10]       burst 4, get coins 1 * 4 * 10 = 40
nums = [10]          burst 10, get coins 1 * 10 * 1 = 10

Total coins 20 + 200 + 40 + 10 = 270

区间动态规划

从最后一个扎破的位置下手，

如果f[i][j]是从i开始到j的最大金币值，

那么我们可以通过枚举最后扎破的位置获得不同的区间，并求最大值

f[i][j] = max(f[i][k - 1] + f[k + 1][j] + midValue), midValue = nums[i - 1] * nums[j + 1] * nums[k]， k是在i 和 j的范围内

对于0点和n - 1点，可以扩大数组两端包括两个1不影响获得的金币数，然后取1到n作为结果(此时数组长度为0，n + 1)

注意在k==left 或 k==right时枚举的气球是左边界或右边界，所以f[i][k - 1]和f[k + 1][j]不需要加入运算

public class Solution {
    /*
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
    public int maxCoins(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }

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


        for (int len = 1; len <= nums.length; len++) {
            for (int left = 1; left <= nums.length - len + 1; left++) {

                int right = left + len - 1;
                for (int k = left; k <= right; k++) {
                    int cur = nums_new[left - 1] * nums_new[right + 1] * nums_new[k];
                    if (k != left) {
                        cur += f[left][k - 1];
                    }

                    if (k != right) {
                        cur += f[k + 1][right];
                    }


                    f[left][right] = Math.max(f[left][right], cur); 
                }
            }
        }
        return f[1][nums.length];
    }



}