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

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

## Solution: (Bottom Up DP)

```cpp
class Solution
{
public:
    int maxCoins(vector<int> &nums)
    {

        int n = nums.size();
        nums.push_back(1);
        nums.insert(nums.begin(), 1);

        vector<vector<int>> v(n + 2, vector<int>(n + 2, 0));

        for (int k = 1; k <= n; k++)
        {
            for (int left = 1; left <= n - k + 1; left++)
            {
                int right = left + k - 1;

                for (int j = left; j <= right; j++)
                {
                    int newVal = nums[left - 1] * nums[j] * nums[right + 1] + v[left][j - 1] + v[j + 1][right];
                    v[left][right] = max(v[left][right], newVal);
                }
            }
        }
        return v[1][n];
    }
};
```

**Time Complexity:- O(n^3)**\
**Space Complexity:- O(2n)**
