Problem Statement

Given n balloons, indexed from 0 to n-1, each balloon is painted with a number on it represented by an array nums. Burst all the balloons.

If the ith balloon is burst, the coins obtained are nums[i-1] * nums[i] * nums[i + 1]. If i - 1 or i + 1 goes out of bounds of the array, treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins that can be collected by bursting the balloons wisely.

Examples

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, 2, 3, 4]
Output: 40

Explanation:
nums = [1, 2, 3, 4] --> [1, 2, 4] --> [1, 4] --> [4] --> []
coins = 2*3*4 + 1*2*4 + 1*1*4 + 1*4*1 = 40.

Different Approaches

1️⃣ Recursive Approach

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

Approach:

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

Code:

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

Complexity Analysis:

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

2️⃣ Memoization (Top Down) Approach

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

Code:

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

Complexity Analysis:

• Time Complexity:O(N^3), There are total N^2 no. of states. And for each state, we are running a partitioning loop roughly for N times.
• Space Complexity:O(N^2) + Auxiliary stack space of O(N), N^2 for the dp array we are using.