Burst Balloons Problem

Burst Balloons problem is one of the classical problems of Dynamic Programming. Let us understand the problem in detail in order to get a Solution to the Burst Balloons Problem.

You are given n balloons with indices ranging from 0 to N - 1. Each balloon has a number painted on it, which is represented by an array 'nums'. You are instructed to burst all of the balloons.

You will receive (nums[i - 1] * nums[i] * nums[i + 1]) coins if you burst the i^th balloon where (0<i<nums.length-1)

If i - 1 or i + 1 is beyond the array's limits, consider it as if it were a balloon with a 1 painted on it. Burst the Balloons in such a way that you get the maximum number of coins.

Let us see some Example Testcases.

TestCase 1

Input : [4,1,6,9,3,7]

Output : 794

TestCase 2

Input : [5,5,5,5,5]

Output : 405

TestCase 3

Input : [4]

Output : 4

Here is the Approach that we use to solve this problem. we can solve this either by memoization or by using a recursive approach.

In order to solve the greater problem, we have to solve this problem at smaller problems. we will get answers to another subarray on basis of answers of other smaller subarrays.

Solution using Memoization

Solution to Burst Balloons Problem in C++

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size() + 2;        
        vector<vector<int>> dp(n, vector<int>(n));
        vector<int> arr(n, 1);
        int i = 1;
        for(int x : nums) {
            arr[i++] = x;
        }
        for(int g = 2; g <= n; g++) { 
          
            for(int i = 0; i <= n - g; i++) {
                int j = i + g - 1;
                
                for(int k = i + 1; k < j; k++) { 
  dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

Solution to Burst Balloons Problem in Java

class Solution {
    public int maxCoins(int[] arr) {
          int[][] dp = new int[arr.length][arr.length];
      
          for(int g = 0; g < dp[0].length; g++) {
              for(int i = 0, j = g; j < dp[0].length; i++, j++) {
                  int max = Integer.MIN_VALUE;

                  for(int k = i; k <= j; k++) {
                      int fin_ans = 0;
                      if(k - 1 >= i)
                          fin_ans += dp[i][k-1];
                      if(k + 1 <= j)
                          fin_ans += dp[k+1][j];
                      int ans = arr[k];
                      if(i - 1 >= 0)
                          ans *= arr[i-1];
                      if(j + 1 < arr.length)
                          ans *= arr[j+1];
                      fin_ans += ans;

                      if(fin_ans > max)
                          max = fin_ans;
                  }
                  dp[i][j] = max;
              }
          }
          return dp[0][dp[0].length - 1];
    }
}