# **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 `i`

balloon, you will get ^{th}`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:167Explanation: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^{3}

__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

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.