LeetEye LeetEye
Hard 2D Dynamic Programming ~5 min

Burst Balloons

2d-dp 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.

Examples

Example 1
Input: nums = [3,1,5,8]
Output: 167
Example 2
Input: nums = [1,5]
Output: 10
Key Insight

Think backwards: which balloon is burst LAST in a range?

Think backwards: which balloon k is burst LAST in range (i,j)? It sees boundaries i,j. Coins = nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j].

How to Approach This Problem

Pattern Recognition: When you see keywords like burst balloons 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 Thinking "which balloon to burst first" is hard because:
Answer: A and B
After bursting, neighbors change. Left and right subproblems depend on what was burst.
2 "Which balloon to burst LAST in range" works because:
Answer: Both
If k is last in (i,j), left side (i,k) and right side (k,j) are solved independently first.
3 If balloon k is burst last in range (i, j):
Answer: Coins = nums[i] * nums[k] * nums[j]
When k is last, all others are gone. k sees boundaries i and j.
4 dp[i][j] represents:
Answer: Max coins for balloons between indices i and j (exclusive)
Range (i, j) means balloons from i+1 to j-1. Boundaries i and j remain.
5 dp[i][j] = max over k of:
Answer: nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j]
Burst k last (gets i*k*j coins), plus best for left and right subranges.

Solution

def maxCoins(nums: List[int]) -> int:
    # Add boundary balloons with value 1
    nums = [1] + nums + [1]
    n = len(nums)
    
    # dp[i][j] = max coins for range (i, j) exclusive
    dp = [[0] * n for _ in range(n)]
    
    # Fill by increasing range length
    for length in range(2, n):  # length = j - i
        for i in range(n - length):
            j = i + length
            # Try each k as last balloon to burst in (i, j)
            for k in range(i + 1, j):
                coins = nums[i] * nums[k] * nums[j]
                dp[i][j] = max(dp[i][j], dp[i][k] + coins + dp[k][j])
    
    return dp[0][n - 1]

Complexity Analysis

Time O(n³)
Space O(n²)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye