LeetCode - Burst Balloons

BurstBalloons.java

// 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.

// 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
// Credits:
// Special thanks to @dietpepsi for adding this problem and creating all test cases.

// solution 1 --- divide and conquer
public int maxCoins(int[] nums) {
    if(nums.length == 0) return 0;
    int[] new_nums = new int[nums.length + 2];
    int j = 1;
    for(int i = 0; i < nums.length; i++){
        if(nums[i] != 0){
            new_nums[j++] = nums[i];
        }
    }
    new_nums[0] = 1; new_nums[j] = 1;
    int[][] memo = new int[j + 1][j + 1];
    return burst(new_nums, memo, 0, j);
}

private int burst(int[] nums, int[][] memo, int left, int right){
    if(left + 1 == right) return 0;
    if(memo[left][right] > 0) return memo[left][right];
    int res = 0;
    for(int i = left + 1; i < right; i++){
        res = Math.max(res, nums[left] * nums[right] * nums[i] 
        + burst(nums, memo, left, i) + burst(nums, memo, i, right));
    }
    memo[left][right] = res;
    return res;
}

// solution 2 --- dp
public int maxCoins(int[] nums) {
    if(nums.length == 0) return 0;
    int[] new_nums = new int[nums.length + 2];
    int n = 1;
    for(int i = 0; i < nums.length; i++){
        if(nums[i] != 0){
            new_nums[n++] = nums[i];
        }
    }
    new_nums[0] = 1; new_nums[n] = 1;
    int[][] dp = new int[n + 1][n + 1];
    
    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++){
                dp[left][right] = Math.max(dp[left][right], 
                    new_nums[left] * new_nums[i] * new_nums[right] + dp[left][i] + dp[i][right]);
            }
        }
    }
    return dp[0][n];
}