312. Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [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

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

• n == nums.length

• 1 <= n <= 500

• 0 <= nums[i] <= 100

Solution

Intuitive idea: Brute force: Compute the Coins for each combination O(N!)

Further anlysis:

DP:

We found the problem itself can be divided into small probems.

For example : main problem :[2, 3, 4, 5, 7] -> choose 4 -> gained 345 -> [2, 3, 5, 7], it is anothe sub problem with smaller scale

so, the next problem is how to divide the problem into sub-problem.

-> we observe that: when we pick nums[i] as the last balloon to burst, then we can seperate the orginal problem into the left sub problem [0....i] and right[i+1....n]

To better computation the result, we add subffix and posFix '1' to the orignal nums, [nums[0], nums[1], nums[2], ... nums[n] ] -> [1, nums[0], nums[1], .... nums[n], 1]

So, we don't need to take care of the left and right of the range. it is just for us to compute results. we don't need to consider if we choose those values as the last burst balloon.

int[][] memo;
public int maxCoins(int[] nums){
    int n = nums.length;
    int newNums = new int[n+2];
    newNums[0] = 1;
    int i = 1;
    for(int num : nums) {
        if(num != 0) {
            newNums[i++] = num;
        }
    }
    newNums[i] = 1;
    memo = new int[i+1][i+1];
    return maxCoins(newNums, 0, i); 
}

public int maxCoins(int[] nums, int left, int right){
    if(left+1 == right) return 0;
    if(memo[left][right] != 0) return memo[left][right];
    
    int max = 0;
    for(int i = left+1; i < right; i++) {
        max = Math.max(max, 
                nums[left]*nums[i]*nums[right] + maxCoins(nums, left, i) + maxCoins(nums, i, right);)
    }
    memo[left][right] = max;
    return max;
}