Problem 59 · Dynamic Programming

Burst Balloons

HardClassic DSA & systems

01Problem

Bursting balloon i earns nums[left]*nums[i]*nums[right] where left/right are current neighbors (out of bounds = 1). Return the maximum coins from bursting all balloons.

02Key insight

Think about the LAST balloon burst in an interval: its neighbors are the fixed interval boundaries, which makes subproblems independent. Interval DP over padded array.

03Solution

solution.pypython12 lines

def max_coins(nums: list[int]) -> int:
    vals = [1] + [x for x in nums if x > 0] + [1]  # zeros never add coins
    n = len(vals)
    dp = [[0] * n for _ in range(n)]  # dp[l][r]: best for open interval (l, r)
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            edge = vals[left] * vals[right]
            dp[left][right] = max(
                dp[left][k] + edge * vals[k] + dp[k][right] for k in range(left + 1, right)
            )
    return dp[0][n - 1]

Try it first.

TimeO(n^3)

SpaceO(n^2)

tests.py · 4 passing

tests.pypython4 lines

assert max_coins([3,1,5,8]) == 167
assert max_coins([1,5]) == 10
assert max_coins([]) == 0
assert max_coins([0, 2]) == 2

04Staff-level follow-up

Recognising 'choose last, not first' generalises: matrix-chain multiplication and optimal query join ordering in Snowflake/Spark optimizers use the same interval DP.