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 rightare 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

Solution:

To tackle this problem, we consider the last balloon to burst.

Let's say the last balloon we burst is balloon i, and we have already have optimized solution for i's left balloons and right balloons.

We use f[left][right] to denote the maximum coins we can collect by bursting all balloons between left and right (except left and right).

Therefore, f[left][right] = max(f[left][i] + f[i][right] + nums[left] * nums[i] * nums[right]), for all i that left < i < right.

We insert a 1 on both side of the balloons, which means these two balloons will be the last two that will not burst.

Start with length 3, we calculate the maximum coins we can collect between any three consecutive balloons.

Then with length 4, we calculate the maximum coins we can collect between any four consecutive balloons.

...

Finally, we know the maximum coins we can collect within any range.



Code:

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        for (int i = 1; i < n + 1; i++) {
            arr[i] = nums[i - 1];
        }
        n = n + 2;
        
        int[][] f = new int[n][n];
        for (int k = 2; k < n; k++) {
            for (int left = 0; left < n - k; left++) {
                int right = left + k;
                for (int i = left + 1; i < right; i++) {
                    f[left][right] = Math.max(f[left][right], f[left][i] + f[i][right] + arr[left] * arr[i] * arr[right]);
                }
            }
        }
        return f[0][n - 1];
    }
}