# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/mcm-dp-or-partition-dp/312.-burst-balloons.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.