# 312. Burst Balloons

## Problem Statement

<br>

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

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,1,5,8]
</strong><strong>Output: 167
</strong><strong>Explanation:
</strong>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
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,5]
</strong><strong>Output: 10
</strong></code></pre>

&#x20;

**Constraints:**

* `n == nums.length`
* `1 <= n <= 300`
* `0 <= nums[i] <= 100`<br>

## Intuition

```
Here there is a dependency and we cannot solve like this

             Let say we burst 
              b1 b2 b3 b4 b5
                Simpy  k-1 * k * k+1 wont work
                we burst b3 
                we are putting 1 in place of that, 
                but actually when we will burst b4, in this approach we will consider b3 as 1
                Find the answer, whereas actually we had to consider b2's value and proceed

                Hence this is failing.

Refer the wrong solution below

Actual solution


            Reason for using i-1 * k * j+1
            The one selected as k is going to be bursted last
            Then second last -> ... -> first

            Now , 
            Lets check what is happening , Extra addition of 1's at ends
            eg -> 1 3 1 5 8 1
                  0 1 2 3 4 5

                  Let say k is at 3 i.e 5
                  Now we say it is bursted at last,
                  So logically there will be no one so we multiply by ones to it

                  (i,j) -> (1,4)
                  So nums[i-1] * nums[k] * nums[j+1] is actually 1*5*1

                  Next left moves to (1,3)
                  Now k = 1 let say

                  So This is second last now

                  so Now nums[i-1] * nums[k] * nums[j+1] is actually 1*3*5 Which is correct

                  So on 
```

### Links

<https://leetcode.com/problems/burst-balloons/description/>

### Video Links

<https://www.youtube.com/watch?v=Yz4LlDSlkns&ab_channel=takeUforward>

### Approach 1:

```
Wrong sol
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int find_ans(vector<int>& nums, int i, int j){
        if( i>j )
            return 0;

        int maxi = INT_MIN;

        for(int k=i; k<=j; k++){
            int left = (k == 0) ? 1 : nums[k-1];
            int right = (k == nums.size()-1) ? 1 : nums[k+1];
            int burst = left * nums[k] * right;
            int temp = nums[k];
            nums[k] = 1;

            int cost = burst + find_ans(nums, i, k-1) 
                                            + find_ans(nums, k+1, j); 

            nums[k] = temp;

            maxi = max(cost, maxi);

            /*
             Here there is a dependency and we cannot solve like this

             Let say we burst 
              b1 b2 b3 b4 b5

                we burst b3 
                we are putting 1 in place of that, 
                but actually when we will burst b4, in this approach we will consider b3 as 1
                Find the answer, whereas actually we had to consider b2's value and proceed

                Hence this is failing.

             */
        }

        return maxi;
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();

        return find_ans(nums, 0, n-1);
    }
};
```

{% endcode %}

### Approach 2:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int find_ans(vector<int>& nums, int i, int j, vector<vector<int>> &dp){
        if( i>j )
            return 0;

        if(dp[i][j] != -1)
            return dp[i][j];

        int maxi = INT_MIN;

        for(int k=i; k<=j; k++){
            int cost = nums[i-1] * nums[k] * nums[j+1] + find_ans(nums, i, k-1, dp) 
                                            + find_ans(nums, k+1, j, dp); 

            maxi = max(cost, maxi);

            /*
            Reason for using i-1 * k * j+1
            The one selected as k is going to be bursted last
            Then second last -> ... -> first

            Now , 
            Lets check what is happening , Extra addition of 1's at ends
            eg -> 1 3 1 5 8 1
                  0 1 2 3 4 5

                  Let say k is at 3 i.e 5
                  Now we say it is bursted at last,
                  So logically there will be no one so we multiply by ones to it

                  (i,j) -> (1,4)
                  So nums[i-1] * nums[k] * nums[j+1] is actually 1*5*1

                  Next left moves to (1,3)
                  Now k = 1 let say

                  So This is second last now

                  so Now nums[i-1] * nums[k] * nums[j+1] is actually 1*3*5 Which is correct

                  So on 
            */
        }

        return dp[i][j] = maxi;
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+1, vector<int> (n+1,-1));

        return find_ans(nums, 1, n, dp);
    }
};
```

{% endcode %}

### Approach 3:

```
Tabulation
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int> (n+2, 0));

        for(int i=n; i>=1; i--){
            for(int j=1; j<=n; j++){
                if(i>j)
                    continue;

                int maxi = INT_MIN;

                for(int k=i; k<=j; k++){
                    int cost = nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j];
                    // For j == n then  j+1 can be out of bound if n+1 array declared 
                    // Therefore declare array of size n+2
          

                    maxi = max(cost, maxi);
                }

                dp[i][j] = maxi;
            }
        }

        return dp[1][n];
    }
};
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###