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.

Example：

Input: [3,1,5,8]
Output: 167
Explanation: 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

Note：

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

解释下题目：

给定一个数组，然后移除一个数字，这个数字和它左边，它右边的数字，这三个数字乘起来就是你能得到的分值，然后继续往复，直到把全部的气球打掉，求出最大的分值。

1. DP

实际耗时：6ms

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

    // init new array
    int[] num = new int[nums.length + 2];
    num[0] = 1;
    num[nums.length + 1] = 1;
    for (int i = 0; i < nums.length; i++) {
        num[i + 1] = nums[i];
    }
    System.out.println(Arrays.toString(num));

    // start dp
    int[][] dp = new int[num.length][num.length];
    for (int i = 2; i < num.length; i++) {
        for (int left = 0; left < num.length - i; left++) {
            int right = left + i;
            for (int j = left + 1; j < right; j++)
                dp[left][right] = Math.max(dp[left][right], num[left] * num[j] * num[right] + dp[left][j] + dp[j][right]);
        }
    }
    return dp[0][num.length - 1];
}

  这是我做过的比较难的DP题目了。拿到题目首先想到的是用暴力。暴力的话，相当于时间复杂度是O(n!)，这显然是不能接受的，肯定需要优化，所以当时想的是，因为最小的数字乘起来肯定是亏的，所以我想的是找到整个数组中最小的数，然后把它打掉，，这样就能有效减少遍历次数；但是！这是不可行的，样例就是一个反例.....所以这种方法放弃，故只能转而寻找动态规划的方法。
  其实动态规划也想了半天，下不去手，因为实在选不出应该先打破哪个气球，主要是你打破任意一个气球之后，都会影响到后面的，实在找不出解决办法，最后去网上看了这篇解法，豁然开朗，你不要想着打破哪个，而是保留哪个，这应该也是这个算法最难的地方了，其他地方参考那篇解法，写的很赞了。

时间复杂度O(n^3)

空间复杂度O(n^2)