LeetCode 312 · 2-D DP

Burst Balloons, explained with a picture

Choosing which balloon pops last.

Hard2-D DP
▶ Watch it step by step

The problem

Balloons have numbers. Popping balloon i earns left × i × right, using its current neighbours (a missing neighbour counts as 1). Pop all balloons in the order that earns the most coins.

Input:  [3, 1, 5, 8]
Output: 167

Picture it

Picture a row of balloons with an unpoppable 1-balloon at each end. Thinking about which balloon pops first is messy, because neighbours keep changing. Instead, for each stretch, choose which balloon pops last: at that moment its neighbours are the stretch’s fixed ends, and the left and right parts can be solved independently.

How to recognise it

  • You remove items from a row, and the score of each removal depends on its current neighbours, which change as items disappear.
  • The final answer is the best over all orders of removal.
  • Thinking about the first removal is messy, because it changes the neighbours of everything else.
  • Thinking about the last item removed in a stretch makes the two sides independent.
  • Up to 300 items allows an O(n³) solution but rules out trying orders.

Start with brute force

Try every item as the next one to pop, score it with its current neighbours, and recurse on the remaining row.

from functools import lru_cache

def burst_brute(nums):
    @lru_cache(None)
    def go(row):                      # row is a tuple of balloons still alive
        best = 0
        for i in range(len(row)):
            left = row[i - 1] if i > 0 else 1
            right = row[i + 1] if i + 1 < len(row) else 1
            best = max(best, left * row[i] * right + go(row[:i] + row[i + 1:]))
        return best
    return go(tuple(nums))

Without the cache there are n! pop orders (10! is already 3.6 million). Even with the cache there is one state for each subset of balloons that are still alive, so up to 2^n states. For n = 300 neither is possible.

From brute force to the idea

  1. Find the problem. If you choose the first balloon to pop in a stretch, the stretch splits into two parts that still affect each other: popping a balloon changes the neighbour of the balloons next to it.
  2. Flip the question. Choose the last balloon k to pop between two fixed boundaries l and r. When k is popped last, everything else strictly between l and r is already gone, so its neighbours are exactly b[l] and b[r]. Its score is b[l] * b[k] * b[r].
  3. The two sides split cleanly. Balloons between l and k and between k and r are popped before k, and each side only sees k and its own boundary, so the two sides are independent: best[l][k] + best[k][r].
  4. Pad the row. b = [1] + nums + [1] adds imaginary 1-balloons that are never popped, so the edges need no special cases.
  5. Fill by gap size. best[l][r] is the best score for popping everything strictly between l and r. A pair at distance gap needs only smaller gaps, so the loops go from gap 2 upwards. The answer is best[0][n-1].

This is the key idea: choose the last balloon in each stretch, and the sides become separate smaller problems.

The key idea

Interval DP: dp[l][r] = max over k of dp[l][k] + dp[k][r] + v[l]·v[k]·v[r]. O(n³).

Python solution

def max_coins(nums):
    b = [1] + nums + [1]                 # imaginary 1-balloons at the ends
    n = len(b)
    best = [[0] * n for _ in range(n)]   # best[l][r]: pop everything strictly between
    for gap in range(2, n):
        for l in range(n - gap):
            r = l + gap
            for k in range(l + 1, r):     # k is the LAST balloon popped in (l, r)
                best[l][r] = max(best[l][r],
                                 best[l][k] + b[l] * b[k] * b[r] + best[k][r])
    return best[0][n - 1]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n!) without the cache; up to O(2^n · n) with itO(2^n): one cached value per subset
Interval DP (shown code)O(n³): about n²/2 pairs (l, r), each trying up to n values of k, roughly n³/6 steps in totalO(n²): the table

For n = 300 that is about 4.5 million inner steps, which takes around a second in Python.

Edge cases

  • Empty list: the loops do nothing and the code returns 0.
  • One balloon ([7]): returns 7, since both neighbours are the imaginary 1s.
  • Two balloons ([1, 5]): returns 10 (pop 1 first for 5, then 5 for 5).
  • Zeros: [0] and [0, 0] both return 0, and a zero in the middle simply scores nothing when popped.
  • Equal values ([2, 2, 2]): returns 14.
  • The padding: without the two 1s, [3, 1, 5, 8] gives 135, not 167.

Common mistakes

  • Choosing the first balloon to pop in each stretch, which does not split the problem into independent sides.
  • Popping the smallest balloon first, a plausible greedy that gives 78 on [3, 1, 5, 8] instead of 167.
  • Letting k run over range(l, r + 1) instead of range(l + 1, r), which scores the boundaries as if they were popped.
  • Forgetting the padding, so edge balloons lose a neighbour.
Your turn: cutting a stick

A stick of length n is cut at the given positions. Each cut costs the length of the piece being cut. Find the cheapest total cost, choosing the order of cuts. For n = 7 and cuts [1, 3, 4, 5] the answer is 16. Describe your approach, then write it if you like.

Compare with our answer

Same interval shape: add the two ends to the cut positions, and for each stretch choose which cut is made first. Its cost is the stretch length, and the two sides are then independent.

def min_cut_cost(n, cuts):
    c = [0] + sorted(cuts) + [n]
    m = len(c)
    cost = [[0] * m for _ in range(m)]
    for gap in range(2, m):
        for l in range(m - gap):
            r = l + gap
            cost[l][r] = min(cost[l][k] + cost[k][r]
                             for k in range(l + 1, r)) + c[r] - c[l]
    return cost[0][m - 1]

It gives 16 for the example, 22 for n = 9 with cuts [5, 6, 1, 4, 2], and 0 when there are no cuts. Time O(m³), space O(m²).

A strong answer mentions: adding the ends, minimising instead of maximising, and choosing the first cut here because the cost depends on the whole piece.

Check what stuck

1. You may split a row of items into stretches, and removing an item scores according to its current neighbours. Which idea usually splits the problem into independent parts?

2. Why is the shown code O(n³) rather than O(n!)?

3. A learner changes the innermost loop to for k in range(l, r + 1). What does max_coins([3, 1, 5, 8]) return?

Score 60% or more and the lesson is marked complete.