DP 51. Burst Balloons | Partition DP | Interactive G-Meet Session Update

1. Problem Statement & Overview

Given an array of $n$ balloons, each with a specific integer number written on it, you must burst all the balloons. Every time you burst a balloon at index i, you receive coins calculated by multiplying the numbers on its left, the balloon itself, and its right neighbor:

\text{Coins} = A[\text{left}] \times A[i] \times A[\text{right}]

Once a balloon is burst, its left and right neighbors become adjacent to each other. The objective is to determine the maximum total coins you can collect by choosing an optimal order to burst all the balloons.

2. Naive Approach vs. Why It Fails

The Forward Thinking Trap

At first glance, this problem resembles Matrix Chain Multiplication (MCM) because you can choose any balloon to burst first, which splits the problem into sub-problems.

Naive Idea: Pick any balloon $b_k$ as the first to burst, calculate the coins earned, and then recursively solve the remaining left sub-array and right sub-array independently.
Why it Fails (Broken Sub-Problem Independence): When you burst a balloon, the neighboring relationships change permanently. If you burst a balloon in the middle, the sub-problem on the left and the sub-problem on the right are not independent. A balloon on the boundary of the left sub-problem might eventually need to multiply with a balloon from the right sub-problem when it is finally burst. Because sub-problems depend on external state changes, standard memoization or dynamic programming breaks down.

3. Core Mental Model: The Reverse Thinking Strategy

To solve the dependency issue, we flip our perspective entirely:

Real-Life Analogy / Mental Hook: Instead of deciding which balloon to burst first, we ask: "Which balloon will be the very last one to burst in this range?"

By thinking in reverse:

If we pick balloon $k$ as the last balloon to burst in a given range [i, j], we are guaranteed that all other balloons in that range have already been cleared out.
Therefore, the immediate left and right multipliers for balloon $k$ are strictly the boundaries outside our current range (i.e., $A[i-1]$ and $A[j+1]$ ).
This completely isolates the left sub-problem [i, k-1] and the right sub-problem [k+1, j], making them 100% independent.

4. Handling Boundary Conditions (Padding)

To prevent out-of-bounds errors when a balloon has no left or right neighbor, we pad the array by inserting 1 at both the beginning and the end.

CODE

Original Array:    [3, 1, 5, 8]
Padded Array:  [1, 3, 1, 5, 8, 1]
Index mapping:  0  1  2  3  4  5  6

Inserting 1 at the ends ensures that when we evaluate the edge balloons, multiplying by 1 yields the correct mathematical coin value without special conditional checks.

5. Recursive Formulation & Mathematical Definition

Let f(i, j) represent the maximum coins obtained by bursting all balloons strictly within the range from index i to index j.

Base Case: If i > j, there are no balloons left in the range to burst. The cost returned is 0.
Recursive Transition: For a chosen last-burst balloon at index index (where i <= index <= j), the total coins earned are:

\text{Cost} = A[i-1] \times A[\text{index}] \times A[j+1] + f(i, \text{index}-1) + f(\text{index}+1, j)

Since we want to maximize the coins, we iterate index through every position from i to j and take the maximum:

f(i, j) = \max_{i \le \text{index} \le j} \Big( A[i-1] \times A[\text{index}] \times A[j+1] + f(i, \text{index}-1) + f(\text{index}+1, j) \Big)

6. Memoized Recursive Solution (Top-Down DP)

By caching overlapping sub-problem states in a 2D DP table initialized to -1, we eliminate redundant exponential computations.

C++ Implementation

C++

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
private:
    int solve(int i, int j, vector<int>& a, vector<vector<int>>& dp) {
        // Base case: invalid range
        if (i > j) return 0;
        
        // Return cached result if already computed
        if (dp[i][j] != -1) return dp[i][j];
        
        int maxi = INT_MIN;
        
        // Try every balloon in range [i, j] as the LAST one to be burst
        for (int index = i; index <= j; index++) {
            int cost = (a[i - 1] * a[index] * a[j + 1]) 
                     + solve(i, index - 1, a, dp) 
                     + solve(index + 1, j, a, dp);
            
            maxi = max(maxi, cost);
        }
        
        return dp[i][j] = maxi;
    }

public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        // DP table for memoization
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1));
        return solve(1, n, nums, dp);
    }
};

7. Tabulated Solution (Bottom-Up DP)

To convert the top-down memoized solution into a bottom-up iterative approach:

Base Cases: dp[i][j] = 0 when i > j. We initialize the DP table with zeros.
Loop Directions:
- Since top-down recursion starts from 1 to n, bottom-up tabulation computes smaller sub-problems first by iterating i from n down to 1, and j from i to n (or using length-based iteration).

C++ Tabulation Code

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        
        // DP table with size (n+2) x (n+2) initialized to 0
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        
        // Bottom-up computation
        for (int i = n; i >= 1; i--) {
            for (int j = i; j <= n; j++) {
                int maxi = 0;
                
                for (int index = i; index <= j; index++) {
                    int cost = (nums[i - 1] * nums[index] * nums[j + 1]) 
                             + dp[i][index - 1] 
                             + dp[index + 1][j];
                    
                    maxi = max(maxi, cost);
                }
                
                dp[i][j] = maxi;
            }
        }
        
        return dp[1][n];
    }
};

8. Complexity Analysis

Approach	Time Complexity	Space Complexity	Rationale
Recursive (Naive)	$O(3^n)$	$O(n)$	Exponential branching without memoization.
Memoized (Top-Down)	$O(n^3)$	$O(n^2) + O(n)$ stack	$n^2$ states, with an inner loop running $O(n)$ times per state.
Tabulated (Bottom-Up)	$O(n^3)$	$O(n^2)$	Two nested loops for bounds `i` and `j` ( $O(n^2)$ states) plus inner loop `index` ( $O(n)$ ).

9. Summary and Key Takeaways

Partition DP Paradigm: Burst Balloons is a classic Partition DP problem where the optimal solution is built by finding the best split point within a range.
Reverse Thinking Principle: Instead of picking the first element to process, framing the choice around the last element executed resolves dependency issues between sub-problems.
Sub-Problem Independence: By assuming balloon $k$ is burst last in range [i, j], its left and right boundaries are strictly locked to $A[i-1]$ and $A[j+1]$ , making sub-problems [i, k-1] and [k+1, j] completely independent.
Padding Technique: Inserting 1 at both ends of the input array safely eliminates boundary check exceptions during coin calculations.
Complexity Profile: Both Top-Down Memoization and Bottom-Up Tabulation achieve an optimal $O(n^3)$ time complexity and $O(n^2)$ space complexity.