
### Problem Statement

###### 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.

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

**Steps To Solve**

- Think of solution without code

  - Lets consider balloons a,b,c,d,e,f.
  - If we burst a we get a\*b money , if we burst b we get a\*b\*c money.
  - Lets burst ballons in order b,e,a,f,c,d we get money a\*b\*c + d\*e\*f +a\*c +d\*f +c\*d + d .And remaining balloons at each stage of burst looks like [acdef,acdf,cdf,cd,d,''].
  - Here number of ways to burst balloon is 6! and we have to find the one which gives us maximum coins.
  - Lets take another example **[2,3,1,5,6,4]** , if the last balloon burst is 2 we have 0+costs(2,3,1,5,6,4) + 1\*2\*1.Similarly if the last balloon burst is 5 we have cost(2,3,1) + cost(6,4) + 1\*5\*1.Similarly we calculate for other balloons as well and the maximum value among them is our maximum coins.
  - Each block in this matrix represent the number of coins we can get by busting balloons from leftmost non crossed value till that column value.
  - Example : [0][1] will contain value of busting balloon 23 from the array.[1][4] will contain value of busting balloon 3156 from the array.And all the diagonal will contain the cost of busting only one balloon in the whole array.Example [0][0] will contain value of busting balloon 2 from the array i.e 1\*2\*3 = 6.
  - Lets calculate for [0][1] i.e **23**.If we bust 2 1st and then 3 , we have 1\*2\*3 + 1\*3\*1 = 9. If we bust 3 1st than 2 we have 2\*3\*1 + 1\*2\*1 = 8. So we take max of them i.e 9 coins.
    | |2| 3 | 1 | 5 | 6 | 4 |
    | --- | --- | --- | --- | --- |---|---|
    | 2| 6|9 | | | | |
    | 3|❌ |6 |45 | | | |
    | 1| ❌|❌ |15 |105 | | |
    | 5| ❌| ❌| ❌|30 |140 | |
    | 6| ❌|❌ |❌ | ❌|120 |140 |
    | 4| ❌|❌ | ❌| ❌|❌ |24 |
  - Now let us make generic solution by taking [1][4] ,i.e cost of busting 3156. So if 3 is last to be burst,then cost = 0 + cost(156) stored in [0][4] position + 2\*3\*4 as 156 is already burst and our array is **[2,3,1,5,6,4]**.If 1 is last to be burst,then cost = cost(3) + cost(56) + 2\*1\*4.If 5 is last to be burst,then cost = cost(31) + cost(6) + 2\*5\*4.If 6 is last to be burst,then cost = cost(315) + 0 + 2\*6\*4.We will then take maximum among them.
  - So considering i and j to be at 3 and 6 in **2 _[3156]_ 4** respectively and let k be at 1.dp[i,k-1] + dp[k+1,j]+nums[i-1]\*nums[k]\*nums[j+1] i.e cost(3) + cost(56) + 2\*1\*4.
  - Handle edge case [2315]64.Lets say we burst 3(k) last,then cost will be dp[i,k-1] + dp[k+1,j]+nums[k]\*nums[j+1] as nums[i-1] is not present we remove it from equation.Same for 23[1564].When i = k or j = k we have dp[i,k-1] and dp[k+1,j] as 0.
  - Lets hop to solution.

  ![Burst balloons](https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcSnD2zkyjERzEI6umTxJDb5T0OMflRK0YBflw&usqp=CAU)

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  let N = nums.length;

  if (N === 0) return 0;

  let opt = new Array(N).fill(0).map(() => new Array(N).fill(0));

  for (let len = 0; len < N; len++) {
    for (let i = 0; i + len < N; i++) {
      let j = i + len;

      for (let k = i; k <= j; k++) {
        let left_num = i === 0 ? 1 : nums[i - 1];
        let right_num = j === N - 1 ? 1 : nums[j + 1];

        let left_opt = k === i ? 0 : opt[i][k - 1];
        let right_opt = k === j ? 0 : opt[k + 1][j];

        opt[i][j] = Math.max(
          opt[i][j],
          left_num * nums[k] * right_num + left_opt + right_opt
        );
      }
    }
  }

  return opt[0][N - 1];
};
```

###### Time and Space Complexity

Time Complexity is **O(N&sup3;)**.
Space complexity in this case is **O(N&sup2;)**.
