312. Burst Balloons | Mining Diamonds | Matrix Chain Multiplication | Solution

 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 <= 300
• 0 <= nums[i] <= 100

Solution:

 Let us take the array as [ B1, B2, B3, B4 ] with Bi as the number on the i^th balloon. We can add 1 on the left and right as we can go out of bound, so the array  now becomes

[ 1, B1, B2, B3, B4, 1 ]

       i                      j

To solve the problem we can take range now as i and j. 

Base Condition: while(i<=j)

so here our index goes from i to j and we solve the subproblem while (i<=j). Let's see the function.

fun(i,j){

    if(i>j)return 0;

int cost=INT_MIN;

for(ind = i->j){

cost=max(cost,arr[i-1]*arr[ind]*arr[j]+fun(i,ind-1)+fun(ind+1,j);

}

return cost;

}

Time Complexity: Exponential (because of overlapping subproblem)

Memoization:

We will make an array dp[n+1][n+1] and for every state i and j we will store the results of fun(i,j). So the Time Complexity will change to N x N x N = N³

Tabulation:

1. Write Base Case

2. See what is changing i.e opposite of recursion ( i -> n to 1, j -> 1 to n)

3. Copy the recurrence