Burst Balloons

Problem

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

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

Return the maximum coins you can collect by bursting the balloons wisely.

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,5]
Output: 10

Constraints:

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

Solution

Approach: Interval DP (Think Backwards)

The key insight is to think backwards: instead of choosing which balloon to burst first, choose which balloon to burst last in a range.

Implementation

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Add 1 at both ends
        nums = [1] + nums + [1]
        n = len(nums)

        # dp[i][j] = max coins from bursting balloons in range (i, j)
        # Exclusive: doesn't include i and j themselves
        dp = [[0] * n for _ in range(n)]

        # Process all ranges by length
        for length in range(2, n):  # Length of range (including boundaries)
            for left in range(n - length):
                right = left + length

                # Try bursting each balloon k last in range (left, right)
                for k in range(left + 1, right):
                    # Coins from bursting k last:
                    # - It's adjacent to left and right at the end
                    # - Plus coins from left and right subranges
                    coins = nums[left] * nums[k] * nums[right]
                    coins += dp[left][k] + dp[k][right]

                    dp[left][right] = max(dp[left][right], coins)

        return dp[0][n-1]

Approach 2: Recursion with Memoization

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        memo = {}

        def dp(left, right):
            # Base case: no balloons to burst
            if left + 1 == right:
                return 0

            if (left, right) in memo:
                return memo[(left, right)]

            max_coins = 0

            # Try bursting each balloon k last
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right]
                coins += dp(left, k) + dp(k, right)
                max_coins = max(max_coins, coins)

            memo[(left, right)] = max_coins
            return max_coins

        return dp(0, len(nums) - 1)

Complexity Analysis

Time Complexity: O(n³), where n is the number of balloons. For each of O(n²) subproblems, we try O(n) positions.
Space Complexity: O(n²) for the dp table or memoization.

Key Insights

Think Backwards: Instead of “which balloon to burst first”, think “which balloon to burst last”.
Last Balloon Benefits: When a balloon is burst last in a range, its neighbors are the range boundaries, making the calculation independent of bursting order within subranges.
Add Boundaries: Add 1s at both ends to handle edge cases uniformly.
Interval DP: dp[i][j] represents the max coins from bursting all balloons strictly between i and j (exclusive).
Independence of Subproblems: Once we decide k is burst last, the left and right subranges are independent.
Range Processing: Process ranges by increasing length, building up from smaller subproblems.
Coins Calculation: When k is burst last in range (i, j):
- coins = nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]