Burst balloons

Understanding:

From the question, we can easily understand that we must burst the balloons in a particular order to collect the maximum number of coins. For example, in the first case, we followed the order: 1, 5, 3, 8 to collect the maximum number of coins i.e. 167. So, the order of bursting the balloons will change the number of coins we can collect. There may be several orders that we can follow.

So, in order to find a valid order, can figure out the first balloon we will burst. Apparently, the entire array(i.e. given) is the range of the elements(i.e. the balloons) and anyone among the elements can be the first.

First, we will try to solve the problem using the technique we have learned in MCM. In the MCM, we selected the matrices sequentially so that the number of scalar multiplication is minimized. Similarly, here we can maintain an order where we will first try to choose the first element, then we can try to find the second one, and so on.

Now, let’s understand if we can really solve the problem using the above approach. Let’s consider the following example:

We are given an array: {b1, b2, b3, b4, b5, b6}. Each element of the given array is representing a balloon. Now, if we burst the b4, we will get a total of (b3*b4*b5) coins. After bursting b4, we are left with the left sub-problem {b1, b2, b3} and the right sub-problem {b5, b6} to solve.

Now, the question is, if we can say that the final answer will be the summation of the current number of coins and the answers from the left and right subproblems. The answer is No.

Let’s understand the reason behind this. Imagine, at first we burst the balloon b4. Then, we are left with the array: {b1, b2, b3, b5, b6}. Now, if we try to burst b3, it will be dependent on b5. Similarly, if we try to burst b5, it will be dependent on b3. Similarly, we can observe the same dependency in the case of other elements as well. So, we cannot solve the subproblems {b1, b2, b3} and {b4, b5} independently as they are dependent on each other.

Intuition:

Until now, we have clearly understood that we cannot solve this problem using this approach. So, we will just try to think in the opposite way. First, we tried to find out a balloon that we will burst first. But now, we will first try to find that balloon which we will burst last.

Note: The intuition is to first find the last balloon, then the second last, and so on. This is the sequence we need to follow to solve this problem. Now, let’s understand how the subproblems are independent in this approach:

Let’s consider the following example:

We are given an array: {b1, b2, b3, b4, b5, b6}. Assume, b4 be the last balloon we will burst. Then we can surely say, the total no. of coins we can get by bursting the balloon b4 is (1*b4*1). Now, we get two subproblems as usual: {b1, b2, b3} and {b5, b6}, and while choosing the second last balloon, we can ensure that b4 exists while bursting the second last balloon. If the second last balloon belongs to the 1st sub-problem i.e. {b1, b2, b3}, it will be only dependent on the last balloon i.e. b4 as the rightmost element will be b4. Similarly, if the second last balloon belongs to the 2nd sub-problem i.e. {b5, b6}, it will also be dependent only on the last balloon i.e. b4 as the leftmost element will be b4. The following illustration will clarify the concept:

Now, we can clearly observe the subproblems are no anymore dependent on each other.

Rules to solve a problem on partition dp:

Marking the array with i, j: We are given an array of balloons of size N. The entire array basically represents the range of the balloons. So, we will place i and j at both ends of the array. Here f(i, ind-1) is the left sub-problem, and f(ind+1, j) is the right sub-problem.

Try all partitions: As we have figured out the logic for marking the i, and j pointers, we will move to the partitioning loop. We can simply write a for loop(say ind) starting from i to j, The problem is being broken in the following manner:

/*It is a pseudocode and it not tied to
any specific programming language*/

f(i, j){
    //Partition loop
    for(int ind = i; ind <= j; ind++){
        cost = a[ind]*a[i-1]*a[j+1] + f(i, ind-1) + f(ind+1, j)
    }
}

Base Case: We can say that when i > j this is not a valid partition and so we will return 0.
Return the best possible answer: Here, in this problem, we are trying to achieve the maximum possible answer i.e. the maximum number of coins. So, among all the costs calculated, we will just store the maximum one. And finally, the maximum cost will be our answer.

/*It is a pseudocode and it not tied to
any specific programming language*/

f(i, j){
    maxi = INT_MIN
    for(int ind = i; ind <= j; ind++){
        cost = a[ind]*a[i-1]*a[j+1] + f(i, ind-1) + f(ind+1, j)
        maxi = max(cost, maxi)
    }
}

The recursive algorithm steps are as follows:

Append 1 to both ends of the given array.
Convert the problem to a recursive function marked by two pointers i and j.
Use a loop to check all possible combinations of balloons and get all possible total numbers of coins.
Return the maximum number of coins we can get.
Base case: If i > j, we will return 0.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Recursive function to calculate
    the maximum coins obtained*/
    int func(int i, int j, vector<int> &nums) {
        if (i > j) return 0;
        int maxCoins = INT_MIN;
    
        // Iterate through each balloon to burst last
        for (int k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            int coins = nums[i - 1] * nums[k] * nums[j + 1];
        
            /* Recursively calculate the maximum 
            coins for the remaining balloons*/
            int remainingCoins = func(i, k - 1, nums) + func(k + 1, j, nums);
        
            // Update the maximum coins
            maxCoins = max(maxCoins, coins + remainingCoins);
        }
        //Return the result
        return maxCoins;
    }
public:
    // Function to calculate the maximum coins obtained
    int maxCoins(vector<int> &nums) {
        int n = nums.size();
    
        // Add 1 to the beginning and end of nums array
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
    
        // Call the helper function to compute maximum coins
        return func(1, n, nums);
    }
};

int main() {
    vector<int> nums = {3, 1, 5, 8};
    
    //Create an instance of Solution class
    Solution sol;
    
    cout << "Maximum coins obtained: " << sol.maxCoins(nums);
    
    return 0;
}

import java.util.*;

class Solution {
    /* Recursive function to calculate 
    the maximum coins obtained*/
    private int func(int i, int j, int[] nums) {
        if (i > j) return 0;
        int maxCoins = Integer.MIN_VALUE;

        // Iterate through each balloon to burst last
        for (int k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            int coins = nums[i - 1] * nums[k] * nums[j + 1];

            /* Recursively calculate the maximum 
            coins for the remaining balloons*/
            int remainingCoins = func(i, k - 1, nums) + func(k + 1, j, nums);

            // Update the maximum coins
            maxCoins = Math.max(maxCoins, coins + remainingCoins);
        }
        // Return the result
        return maxCoins;
    }

    // Function to calculate the maximum coins obtained
    public int maxCoins(int[] nums) {
        int n = nums.length;

        // Add 1 to the beginning and end of nums array
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n);

        // Call the helper function to compute maximum coins
        return func(1, n, newNums);
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 8};

        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("Maximum coins obtained: " + sol.maxCoins(nums));
    }
}
class Solution:
    """ Recursive function to calculate
    the maximum coins obtained"""
    def func(self, i, j, nums):
        if i > j:
            return 0
        maxCoins = float('-inf')

        # Iterate through each balloon to burst last
        for k in range(i, j + 1):
            """ Calculate the coins obtained
            by bursting the k-th balloon last"""
            coins = nums[i - 1] * nums[k] * nums[j + 1]

            """ Recursively calculate the maximum
            coins for the remaining balloons"""
            remainingCoins = self.func(i, k - 1, nums) + self.func(k + 1, j, nums)

            # Update the maximum coins
            maxCoins = max(maxCoins, coins + remainingCoins)
        
        # Return the result
        return maxCoins

    # Function to calculate the maximum coins obtained
    def maxCoins(self, nums):
        n = len(nums)

        # Add 1 to the beginning and end of nums array
        nums = [1] + nums + [1]

        # Call the helper function to compute maximum coins
        return self.func(1, n, nums)

if __name__ == "__main__":
    nums = [3, 1, 5, 8]

    # Create an instance of Solution class
    sol = Solution()

    print("Maximum coins obtained:", sol.maxCoins(nums))
class Solution {
    /* Recursive function to calculate
    the maximum coins obtained*/
    func(i, j, nums) {
        if (i > j) return 0;
        let maxCoins = Number.MIN_VALUE;

        // Iterate through each balloon to burst last
        for (let k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            let coins = nums[i - 1] * nums[k] * nums[j + 1];

            /* Recursively calculate the maximum
            coins for the remaining balloons*/
            let remainingCoins = this.func(i, k - 1, nums) + this.func(k + 1, j, nums);

            // Update the maximum coins
            maxCoins = Math.max(maxCoins, coins + remainingCoins);
        }
        // Return the result
        return maxCoins;
    }

    // Function to calculate the maximum coins obtained
    maxCoins(nums) {
        let n = nums.length;

        // Add 1 to the beginning and end of nums array
        nums = [1, ...nums, 1];

        // Call the helper function to compute maximum coins
        return this.func(1, n, nums);
    }
}

const nums = [3, 1, 5, 8];

// Create an instance of Solution class
const sol = new Solution();

console.log("Maximum coins obtained:", sol.maxCoins(nums));

Complexity Analysis:

Time Complexity: Exponential.

Space Complexity: O(N), As we are using auxiliary stack space of O(N).

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n+1][n+1]: As there are two changing parameters in the recursive solution, 'i' and 'j'. The value of 'i' and 'j' ranges from 1 to n+1. Therefore, we need 2D dp array.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Recursive function to calculate
    the maximum coins obtained*/
    int func(int i, int j, vector<int> &nums, vector<vector<int>> &dp) {
        if (i > j) return 0;
        
        //Check if the subproblem is already solved
        if (dp[i][j] != -1) return dp[i][j];
        
        int maxCoins = INT_MIN;
    
        // Iterate through each balloon to burst last
        for (int k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            int coins = nums[i - 1] * nums[k] * nums[j + 1];
        
            /* Recursively calculate the maximum 
            coins for the remaining balloons*/
            int remainingCoins = func(i, k - 1, nums, dp) + func(k + 1, j, nums, dp);
        
            // Update the maximum coins
            maxCoins = max(maxCoins, coins + remainingCoins);
        }
        //Return the result
        return dp[i][j] = maxCoins;
    }
public:
    // Function to calculate the maximum coins obtained
    int maxCoins(vector<int> &nums) {
        int n = nums.size();
    
        // Add 1 to the beginning and end of nums array
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        // Create a DP array for memoization
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1));
        
        // Call the helper function to compute maximum coins
        return func(1, n, nums, dp);
    }
};

int main() {
    vector<int> nums = {3, 1, 5, 8};
    
    //Create an instance of Solution class
    Solution sol;
    
    cout << "Maximum coins obtained: " << sol.maxCoins(nums);
    
    return 0;
}

import java.util.*;

class Solution {
    /* Recursive function to calculate
    the maximum coins obtained*/
    private int func(int i, int j, int[] nums, int[][] dp) {
        if (i > j) return 0;
        
        // Check if the subproblem is already solved
        if (dp[i][j] != -1) return dp[i][j];
        
        int maxCoins = Integer.MIN_VALUE;

        // Iterate through each balloon to burst last
        for (int k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            int coins = nums[i - 1] * nums[k] * nums[j + 1];
            
            /* Recursively calculate the maximum 
            coins for the remaining balloons*/
            int remainingCoins = func(i, k - 1, nums, dp) + func(k + 1, j, nums, dp);
            
            // Update the maximum coins
            maxCoins = Math.max(maxCoins, coins + remainingCoins);
        }
        // Return the result
        return dp[i][j] = maxCoins;
    }

    // Function to calculate the maximum coins obtained
    public int maxCoins(int[] nums) {
        int n = nums.length;

        // Add 1 to the beginning and end of nums array
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n);

        // Create a DP array for memoization
        int[][] dp = new int[n + 2][n + 2];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // Call helper function to compute maximum coins
        return func(1, n, newNums, dp);
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 8};

        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("Maximum coins obtained: " + sol.maxCoins(nums));
    }
}
class Solution:
    """ Recursive function to calculate
    the maximum coins obtained"""
    def func(self, i, j, nums, dp):
        if i > j:
            return 0
        
        # Check if the subproblem is already solved
        if dp[i][j] != -1:
            return dp[i][j]
        
        maxCoins = float('-inf')

        # Iterate through each balloon to burst last
        for k in range(i, j + 1):
            """ Calculate the coins obtained by
            bursting the k-th balloon last"""
            coins = nums[i - 1] * nums[k] * nums[j + 1]
            
            """ Recursively calculate the maximum
            coins for the remaining balloons"""
            remainingCoins = self.func(i, k - 1, nums, dp) + self.func(k + 1, j, nums, dp)
            
            # Update the maximum coins
            maxCoins = max(maxCoins, coins + remainingCoins)
        
        # Return the result
        dp[i][j] = maxCoins
        return maxCoins

    # Function to calculate the maximum coins obtained
    def maxCoins(self, nums):
        n = len(nums)

        # Add 1 to the beginning and end of nums array
        nums = [1] + nums + [1]

        # Create a DP array for memoization
        dp = [[-1] * (n + 2) for _ in range(n + 2)]

        # Call the helper function to compute maximum coins
        return self.func(1, n, nums, dp)

if __name__ == "__main__":
    nums = [3, 1, 5, 8]

    # Create an instance of Solution class
    sol = Solution()

    print("Maximum coins obtained:", sol.maxCoins(nums))
class Solution {
    /* Recursive function to calculate
    the maximum coins obtained*/
    func(i, j, nums, dp) {
        if (i > j) return 0;
        
        // Check if the subproblem is already solved
        if (dp[i][j] !== -1) return dp[i][j];
        
        let maxCoins = Number.MIN_VALUE;

        // Iterate through each balloon to burst last
        for (let k = i; k <= j; k++) {
            /* Calculate the coins obtained
            by bursting the k-th balloon last*/
            let coins = nums[i - 1] * nums[k] * nums[j + 1];
            
            /* Recursively calculate the maximum 
            coins for the remaining balloons*/
            let remainingCoins = this.func(i, k - 1, nums, dp) + this.func(k + 1, j, nums, dp);
            
            // Update the maximum coins
            maxCoins = Math.max(maxCoins, coins + remainingCoins);
        }
        // Return the result
        dp[i][j] = maxCoins;
        return dp[i][j];
    }

    // Function to calculate the maximum coins obtained
    maxCoins(nums) {
        let n = nums.length;

        // Add 1 to the beginning and end of nums array
        nums = [1, ...nums, 1];

        // Create a DP array for memoization
        let dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(-1));

        // Call the helper function to compute maximum coins
        return this.func(1, n, nums, dp);
    }
}

const nums = [3, 1, 5, 8];

// Create an instance of Solution class
const sol = new Solution();

console.log("Maximum coins obtained:", sol.maxCoins(nums));

Complexity Analysis:

Time Complexity: O(N³), There are total N² no. of states. And for each state, we are running a partitioning loop roughly for N times.

Space Complexity: O(N²) + Auxiliary stack space of O(N), N² for the dp array we are using.

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n+2][n+2]: As the highest value of j can have is 'n' and in that case, it will search for the value arr[j+1] i.e. arr[n+1]. So, to handle this case, we need the size to be n+2.
Handle the base case: We knew in the recursive code the base case was when i > j, it meant that there are no valid partition. So, to cover this case we can initialize the entire dp array with 0.
Next, memoization is a top-down approach, whereas tabulation is bottom-up. Our changing parameters i and j will change in opposite directions, i.e i will change from n→1 and j will change from 1→ n.
After that, copy down the recursive logic inside the nested loops to get the tabulation code.

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:
    // Function to calculate the maximum coins obtained
    int maxCoins(vector<int> &nums) {
        int n = nums.size();
    
        // Add 1 to the beginning and end of nums array
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
    
        // Create a DP array for memoization
        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;
            
                /*  Iterate through each possible
                balloon to burst last*/
                for (int ind = i; ind <= j; ind++) {
                    /* Calculate the coins obtained by
                    bursting the ind-th balloon last*/
                    int coins = nums[i - 1] * nums[ind] * nums[j + 1];
                
                    /* Calculate the maximum coins
                    for the remaining balloons*/
                        int remainingCoins = dp[i][ind - 1] + dp[ind + 1][j];
                
                    // Update the maximum coins
                    maxi = max(maxi, coins + remainingCoins);
                }
                //Store the maximum value in dp table
                dp[i][j] = maxi;
            }
        }
        //Return the result
        return dp[1][n];
    }
};
int main() {
    vector<int> nums = {3, 1, 5, 8};
    
    //Create an instance of Solution class
    Solution sol;
    
    //Print the result
    cout << "Maximum coins obtained: " << sol.maxCoins(nums) << "\n";
    
    return 0;
}

import java.util.*;

class Solution {
    // Function to calculate the maximum coins obtained
    public int maxCoins(int[] nums) {
        int n = nums.length;
        
        // Add 1 to the beginning and end of nums array
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n);
        
        // Create a DP array for memoization
        int[][] dp = new int[n + 2][n + 2];
        
        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= n; j++) {
                if (i > j) continue;
                int maxi = Integer.MIN_VALUE;

                /* Iterate through each possible
                balloon to burst last*/
                for (int ind = i; ind <= j; ind++) {
                    
                    /* Calculate the coins obtained by 
                    bursting the ind-th balloon last*/
                    int coins = newNums[i - 1] * newNums[ind] * newNums[j + 1];

                    /* Calculate the maximum coins
                    for the remaining balloons*/
                    int remainingCoins = dp[i][ind - 1] + dp[ind + 1][j];

                    // Update the maximum coins
                    maxi = Math.max(maxi, coins + remainingCoins);
                }
                // Store the maximum value in dp table
                dp[i][j] = maxi;
            }
        }
        // Return the result
        return dp[1][n];
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 8};

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Print the result
        System.out.println("Maximum coins obtained: " + sol.maxCoins(nums));
    }
}
class Solution:
    # Function to calculate the maximum coins obtained
    def maxCoins(self, nums):
        n = len(nums)
        
        # Add 1 to the beginning and end of nums array
        nums = [1] + nums + [1]
        
        # Create a DP array for memoization
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        
        for i in range(n, 0, -1):
            for j in range(1, n + 1):
                if i > j:
                    continue
                maxi = float('-inf')
                
                """ Iterate through each possible
                balloon to burst last"""
                for ind in range(i, j + 1):
                    """ Calculate the coins obtained by 
                    bursting the ind-th balloon last"""
                    coins = nums[i - 1] * nums[ind] * nums[j + 1]
                    
                    # Calculate the maximum coins for the remaining balloons
                    remainingCoins = dp[i][ind - 1] + dp[ind + 1][j]
                    
                    # Update the maximum coins
                    maxi = max(maxi, coins + remainingCoins)
                
                # Store the maximum value in dp table
                dp[i][j] = maxi
        
        # Return the result
        return dp[1][n]

if __name__ == "__main__":
    nums = [3, 1, 5, 8]
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the result
    print("Maximum coins obtained:", sol.maxCoins(nums))
class Solution {
    // Function to calculate the maximum coins obtained
    maxCoins(nums) {
        let n = nums.length;
        
        // Add 1 to the beginning and end of nums array
        nums = [1, ...nums, 1];
        
        // Create a DP array for memoization
        let dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));
        
        for (let i = n; i >= 1; i--) {
            for (let j = 1; j <= n; j++) {
                if (i > j) continue;
                let maxi = Number.MIN_VALUE;
                
                /* Iterate through each possible 
                balloon to burst last*/
                for (let ind = i; ind <= j; ind++) {
                    
                    /* Calculate the coins obtained by 
                    bursting the ind-th balloon last*/
                    let coins = nums[i - 1] * nums[ind] * nums[j + 1];
                    
                    // Calculate the maximum coins for the remaining balloons
                    let remainingCoins = dp[i][ind - 1] + dp[ind + 1][j];
                    
                    // Update the maximum coins
                    maxi = Math.max(maxi, coins + remainingCoins);
                }
                
                // Store the maximum value in dp table
                dp[i][j] = maxi;
            }
        }
        
        // Return the result
        return dp[1][n];
    }
}

const nums = [3, 1, 5, 8];

// Create an instance of Solution class
const sol = new Solution();

// Print the result
console.log("Maximum coins obtained:", sol.maxCoins(nums));

Complexity Analysis:

Time Complexity:O(N³), There are total N² no. of states. And for each state, we are running a partitioning loop roughly for N times

Space Complexity:O(N²), N² for the dp array we are using.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Understanding:

Intuition:

Rules to solve a problem on partition dp:

The recursive algorithm steps are as follows:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts