Burst Balloons

How it works

We want the maximum coins we can get by bursting balloons in the best order. The key trick is to think in reverse:

Instead of choosing which balloon to burst first, we choose which balloon is burst last in a range.

If we are only looking at balloons between l and r, and balloon i is the last one burst in that range, then:

• all balloons inside (l..r) except i are already gone
• so the neighbors of i are fixed as new_nums[l - 1] and new_nums[r + 1]
• coins gained from bursting i last are:
  • new_nums[l - 1] * new_nums[i] * new_nums[r + 1]

After bursting i last, the remaining problem splits into two independent subproblems:

• best coins for [l .. i-1]
• best coins for [i+1 .. r]

This makes the problem perfect for interval DP.

Steps

1. Create a new array new_nums = [1] + nums + [1] to handle boundaries easily.
2. Let dp[l][r] represent the maximum coins we can collect by bursting balloons from index l to r (inside new_nums).
3. Initialize dp with zeros since empty ranges give 0 coins.
4. Fill the DP table by increasing interval size:
   • iterate l from n down to 1
   • iterate r from l up to n
5. For each interval [l, r], try every balloon i in [l, r] as the last balloon to burst:
   • coins from bursting i last:
     • new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
   • plus the best coins from the left sub-interval:
     • dp[l][i - 1]
   • plus the best coins from the right sub-interval:
     • dp[i + 1][r]
   • take the maximum over all i
6. The final answer is stored in dp[1][n], representing bursting all original balloons.

Complexity

• Time complexity: O(n^3)
• Space complexity: O(n^2)

Things to watch for

Thinking About First Balloon to Burst Instead of Last

The key insight is to consider which balloon is burst LAST in a range, not first. When thinking about the first balloon, the subproblems are not independent because neighbors change. When considering the last balloon, the boundary neighbors are fixed.

Forgetting to Pad the Array with 1s

The problem states that out-of-bounds neighbors are treated as value 1. Forgetting to add 1 at both ends of the array causes index errors or incorrect coin calculations at the boundaries.

Incorrect Loop Order in Bottom-Up DP

In bottom-up DP, smaller intervals must be computed before larger ones. The left index l should iterate in decreasing order while r iterates in increasing order. Wrong iteration order reads uncomputed DP values.

Using Wrong Neighbors in Coin Calculation

When balloon i is the last to burst in range [l, r], its neighbors are nums[l-1] and nums[r+1] (the boundaries), not nums[i-1] and nums[i+1] (adjacent indices).

Not Handling Empty Range Base Case

When l > r, there are no balloons to burst, so the result should be 0. Missing this base case causes incorrect recursion or array index errors.

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        new_nums = [1] + nums + [1]

        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for l in range(n, 0, -1):
            for r in range(l, n + 1):
                for i in range(l, r + 1):
                    coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
                    coins += dp[l][i - 1] + dp[i + 1][r]
                    dp[l][r] = max(dp[l][r], coins)

        return dp[1][n]

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> newNums(n + 2, 1);
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int l = n; l >= 1; l--) {
            for (int r = l; r <= n; r++) {
                for (int i = l; i <= r; i++) {
                    int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
                    coins += dp[l][i - 1] + dp[i + 1][r];
                    dp[l][r] = max(dp[l][r], coins);
                }
            }
        }

        return dp[1][n];
    }
};