Lintcode 168. 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

Example 1:

Input：[4, 1, 5, 10]
Output：270
Explanation：
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

Example 2:

Input：[3,1,5]
Output：35
Explanation：
nums = [3, 1, 5] burst 1, get coins 3 * 1 * 5 = 15
nums = [3, 5] burst 3, get coins 1 * 3 * 5 = 15
nums = [5] burst 5, get coins 1 * 5 * 1 = 5
Total coins 15 + 15 + 5  = 35

Notice

• 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

Analysis:
An interval DP problem. 
We define dp[n + 2][n + 2] where dp[i][j] means from the i + 1 th to j - 1th ballons, the max score we can get. So the transist function would be

dp[i][j] = max (dp[i][k] + dp[k][j] + nums[i - 1] * nums[k - 1] * nums[j + 1]), where i < k < j;
We can think the k is the last ballon we burst. 

Finally we return dp[0][n + 1]

Code (Java):

public class Solution {
    /**
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        
        for (int len = 2; len < n + 2; len++) {
            for (int i = 0; i < n + 2 - len; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++) {
                    int maxScore = dp[i][k] + dp[k][j];
                    int a = i == 0 ? 1 : nums[i - 1];
                    int b = nums[k - 1];
                    int c = j == n + 1? 1 : nums[j - 1];
                    maxScore += a * b * c;
                    
                    dp[i][j] = Math.max(dp[i][j], maxScore);
                }
            }
        }
        
        return dp[0][n + 1];
    }
}

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;
        }
        
        if (nums.length == 1) {
            return nums[0];
        }
        
        int n = nums.length;
        int[] nums2 = new int[n + 2];
        nums2[0] = nums2[nums2.length - 1] = 1;
        
        // nums [2, 3, 4]
        // nums2 [1, 2, 3, 4, 1]
        for (int i = 0; i < nums.length; i++) {
            nums2[i + 1] = nums[i];
        }
        n += 2;
        
        // dp[i][j] means the max score from [i + 1, j - 1]
        // return dp[0][n]
        int[][] dp = new int[n][n];
        
        // init state
        // dp[0][1] = 0, dp[1][2] = 0, dp[2][3] = 0
        
        // transit function
        // dp[i][j] = Math.max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]), where i < k < j;
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}