# 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 ith 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 = N3

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