BurstBalloons.java

package dynamic_programming;

import java.util.Arrays;

/**
 * Created by gouthamvidyapradhan on 02/01/2018.
 * 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

 Solution: O(N ^ 3)
 The recursive top-down dp memorization solution is based on the idea where each balloon is considered as the last
 balloon to be burst.
 For the above example 1,3,1,5,8,1 (1 included at either end to indicate boundary)
 each balloon starting from 3 until 8 is chosen each time as a the last balloon to be burst using the boundary 1 on
 either side.
 So, for the first iteration the result is calculated as
 3*1(left boundary)*1(right boundary) + dp(1, 3) (left-sub-problem having 1 and 3 as the boundary) + dp(3, 1)
 (right-sub-problem having 3 and 1 as the boundary)

 */
public class BurstBalloons {
    private int[][] dp;
    private int[] N;

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        int[] A = {3, 1, 5, 8};
        System.out.println(new BurstBalloons().maxCoins(A));
    }

    public int maxCoins(int[] nums) {
        N = new int[nums.length + 2];
        N[0] = N[N.length - 1] = 1; //boundary
        for(int i = 0; i < nums.length; i ++){
            N[i + 1] = nums[i];
        }
        dp = new int[N.length][N.length];
        for (int[] aDp : dp) {
            Arrays.fill(aDp, -1);
        }
        return dp(0, N.length - 1);
    }

    private int dp(int l, int r){
        if(l + 1 == r) return 0;
        if(dp[l][r] != -1) return dp[l][r];
        int result = 0;
        for(int i = l + 1; i < r; i ++){
            result = Math.max(result, N[i] * N[l] * N[r] + dp(l, i) + dp(i, r));
        }
        dp[l][r] = result;
        return dp[l][r];
    }


}