Burst Balloons

Problem link

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.

Example : 
Input: [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


Discussion :

The base case deals with only a single balloon, in which case the answer is straightforward - we just pop it and collect the coins for it.

Assuming we have N balloons, how do we reduce the problem to smaller sub problems ? We have to pop one or more of the balloons to reduce the problem size. However, which balloon should we pop first ? This is tricky. When we pop a balloon we modify the rest of the system. Also,which one maximizes our profit ? At this point, we notice that we need to change our perspective.

What if instead of choosing a balloon to pop first, we actually choose a balloon to pop last ? so we reduce P(N) to P(N - 1) based on the last balloon to pop. This way, our sub problems are not affected by our decision. But which balloon should we save for last ? anyone of them may end up with a different cost. In such a case we are left with no choice but to try every one of them as the last balloon to pop and pick the one that maximizes our profit.

We'll solve this problem using dynamic programming. The recurrence relation is as follows:

DP[i,j] = max{over all k: DP[i,k - 1] + DP[k + 1,j]  + (B[i - 1] * B[k] * B[j + 1])}

We multiply B[k] (the last balloon to pop) with B[i - 1] and B[j + 1] because we assume that the rest of the balloons betwee i to k and between k to j have been popped already. 

public int maxCoins(int[] nums) {
        int n=nums.length+2;
        int[] newnums=new int[n];
        for(int i=0;i<n-2;i++){
            newnums[i+1]=nums[i];
        }
        newnums[0]=newnums[n-1]=1;
        int[][] DP=new int[n][n];
        for(int k=2;k<n;k++){
            for(int l=0;l+k<n;l++){
                int h=l+k;
                for(int m=l+1;m<h;m++){
                    DP[l][h]=Math.max(DP[l][h],newnums[l]*newnums[m]*newnums[h]+DP[l][m]+DP[m][h]);
                }
            }
        }
        return DP[0][n-1];
    }