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

I wasn't able to find a decent solution until I watched this video from youtube.

The tough part of this problem is any decision you make now will affect the later ones. But if we think it reversely, everything becomes clear.

For example.

3,1,5,8,

If we burst 3 lastly, it will give us 3*1*1+ maxcoin(1,5,8) with left as 3 and right as 1.

If we burst 1 lastly, it will give us 1*1*1+ maxcoin(3) with left as 1 and right as 1 + maxcoin(5,8) with left as 1 and right as 1.

If we burst 5 lastly, it will give us 5*1*1+ maxcoin(3,1) with left as 1 and right as 5 + maxcoin(8) with left as 5 and right as 1.

If we burst 8 lastly, it will give us 8*1*1+ maxcoin(3,1,5) with left as 1 and right as 8.
Among all those 4 cases, we can find a maximum.

We use a 2D array to track all the calculated maximum coin for a given range to avoid repeating recursion and calculation.

  public int maxCoins(int[] nums) {  
     int[][] dp=new int[nums.length][nums.length];  
     return maxHelper(nums,0,nums.length-1,dp);  
   }  
   public int maxHelper(int[] nums, int i, int j,int[][] dp){  
     if(i>j) return 0;  
     if(dp[i][j]!=0) return dp[i][j];  
     int res=0;  
     int left=i-1<0? 1: nums[i-1];  
     int right=j+1>=nums.length? 1: nums[j+1];   
     for(int k=i;k<=j;k++){  
       res=Math.max(res,nums[k]*left*right+maxHelper(nums,i,k-1,dp)+maxHelper(nums,k+1,j,dp));  
     }  
     dp[i][j]=res;  
     return res;  
   }  

Iterative solution
We can calculate dp[0][0],dp[1][1]... dp[n-1][n-1]  range length=0;
then dp[0][1],dp[1][2],dp[n-2][n-1], range length=1
then  range length=2
Exactly as shown in the video, we are able to get dp[0][n-1]
In my solution, k is the range length. i is the range starting index, j is the iterator.

 public int maxCoins(int[] nums) {  
     if(nums==null || nums.length==0) return 0;  
     int[][] dp=new int[nums.length][nums.length];  
     for(int k=0;k<nums.length;k++){  
       for(int i=0;i<nums.length-k;i++){  
         int left=i-1<0? 1: nums[i-1];  
         int right= i+k+1<nums.length? nums[i+k+1]:1;  
         for(int j=i;j<=i+k;j++){  
           int leftHalf=j==i? 0: dp[i][j-1];  
           int rightHalf=j==i+k? 0: dp[j+1][i+k];  
           dp[i][i+k]=Math.max(dp[i][i+k],nums[j]*left*right+leftHalf+rightHalf);  
         }  
       }  
     }  
     return dp[0][nums.length-1];  
   }