312. Burst Balloons

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.

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

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

Video Links

Approach 1:

Wrong sol

C++

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);
    }
};

Approach 2:

Memoization

C++

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);
    }
};

Approach 3:

Tabulation

C++

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];
    }
};

Approach 4:

C++