Interval DP

Problem

The input is a row of things and the choices act on a contiguous range of it: take a stone from the left or right end, burst a balloon and let its neighbours close up, or split a range into two parts. A range of n items has about n²/2 sub-ranges, and each is described by just its two endpoints. If the answer for a range depends only on answers for ranges strictly inside it, you can solve all of them in order of increasing length, in O(n²) cells times the cost of choosing a split.

Intuition

A range is a smaller copy of the whole problem. If you take a stone from the left end of piles l..r, what remains is piles l+1..r, which is the same game on a shorter row. If you choose k as the last balloon to burst in the range (l, r), then before that final burst everything left of k and everything right of k was already gone, and those two sides never interacted because k stood between them the whole time. In both cases the bigger range reduces to smaller ranges.

The trick in balloons is that asking which balloon to burst first is a bad question: afterwards the neighbours change and the remaining problem is not a clean sub-range. Asking which to burst last is good: its neighbours are known (they are the borders of the range), and the two halves are independent sub-ranges of the same shape.

Because every range depends on strictly shorter ranges, fill by increasing length (the "gap" between the endpoints). The usual loop order is gap, then left, with right = left + gap. A plain row-by-row fill would try to read cells that are not yet computed.

Only cells with at least one balloon strictly between the two endpoints are filled. Short ranges (near the diagonal) are computed first and feed the cells up and to the right. The blue corner is the whole row. The diagram scrolls sideways on a narrow screen.

Mechanics

Burst balloons: choose the last one

Pad the row with a 1 at each end, so a burst at the border never reads outside the array. Let coins[l][r] be the most you can earn by bursting every balloon strictly between positions l and r (neither l nor r is burst). If k is burst last in that range, the coins for it are pad[l] * pad[k] * pad[r], since everything else between l and r is already gone and only the borders remain as neighbours. Everything left of k, between l and k, was burst earlier and in isolation from the right side, and likewise on the right. So

coins[l][r] = max over k in (l, r) of coins[l][k] + pad[l]*pad[k]*pad[r] + coins[k][r].

Ranges with nothing strictly between (r = l + 1) are worth 0. The answer is coins[0][n + 1]. Correctness rests on the independence of the two sides: no balloon on the left of k ever has a neighbour on the right of k, since k is still present.

Stone game: score difference

Two players alternate, each taking the pile at either end; both play perfectly. Define diff[l][r] as the best value of (score of the player to move) minus (score of the other player) over piles l..r. Taking the left pile gains piles[l] and leaves the opponent to move on l+1..r, whose own advantage is diff[l+1][r], so that line is worth piles[l] - diff[l+1][r]. The right end is symmetric. A single pile is just its value:

diff[l][r] = max(piles[l] - diff[l+1][r], piles[r] - diff[l][r-1]).

The first player wins when diff[0][n-1] is positive. Since the two scores add to the total, the first player's score is (total + diff) / 2. Subtracting rather than tracking two scores is the key simplification, and it works because the game is zero-sum.

Row l, column r is the margin the mover can force on piles l to r. The amber diagonal is single piles; the blue corner is the whole row. Negative cells are ranges where the player to move is already losing.

When the range only shrinks on one side

In Stone Game II the player to move takes the first x piles of what is left, for any x from 1 to 2M, and M becomes the larger of M and x. The right end never moves, so a range is just a start index, and the state is (start, M). Let best(start, M) be the most stones the mover can collect from there. With suffix sums, taking x piles leaves the opponent at (start + x, max(M, x)), so best(start, M) = max over x of suffix[start] - best(start + x, max(M, x)), and if 2M covers everything left the mover simply takes it all. Memoize on the pair. There are O(n) starts and O(n) values of M, and each tries O(n) moves, so O(n³) in the worst case.

The general split recurrence

Matrix-chain multiplication, optimal binary search trees and minimum-cost triangulation share the shape cost[l][r] = min over k of cost[l][k] + cost[k][r] + join(l, k, r). Recognise it by the question "what is the last (or outermost) operation on this range, and does it cut the range into two independent pieces?".

Worked example

Balloons. For the row 2, 4, 3, 5, padded to 1, 2, 4, 3, 5, 1, the table fills out to 115 coins. The top row is 0, 0, 8, 30, 110, 115. One order that achieves it bursts the balloons at positions 2, 1, 0, 3 (counting from 0) in that sequence; the final one, the balloon worth 5, is alone between the two padded 1s and earns 5 coins.

Stone game. On the piles 3, 1, 4, 1, 5, 9 the table's top row is 3, 2, 2, 5, 0, 9. The first player can force a margin of 9. The total is 23, so the first player collects 16 and the second 7; the first player wins: yes.

Stone Game II. With the same piles, the best the first player can collect when allowed to take 1 to 2M piles from the front is 16 stones out of 23. The memo holds only 4 entries, because most (start, M) pairs are either unreachable or end the game by taking everything left.

Implementation

def max_coins(nums):
    pad = [1] + nums + [1]
    n = len(pad)
    coins = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for left in range(n - gap):
            right = left + gap
            coins[left][right] = max(
                coins[left][k] + pad[left] * pad[k] * pad[right] + coins[k][right]
                for k in range(left + 1, right)
            )
    return coins[0][n - 1]


def first_player_margin(piles):
    n = len(piles)
    diff = piles[:]                      # diff for ranges of length 1
    for gap in range(1, n):
        for left in range(n - gap):
            right = left + gap
            diff[left] = max(piles[left] - diff[left + 1], piles[right] - diff[left])
    return diff[0]

Variations and edge cases

from functools import cache


def stone_game_two(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]

    @cache
    def best(start, m):
        if start + 2 * m >= n:
            return suffix[start]
        return max(suffix[start] - best(start + x, max(m, x)) for x in range(1, 2 * m + 1))

    return best(0, 1)


def min_merge_cost(sizes):
    prefix = [0]
    for s in sizes:
        prefix.append(prefix[-1] + s)
    n = len(sizes)
    cost = [[0] * n for _ in range(n)]
    for gap in range(1, n):
        for left in range(n - gap):
            right = left + gap
            cost[left][right] = min(cost[left][k] + cost[k + 1][right] for k in range(left, right)) + prefix[right + 1] - prefix[left]
    return cost[0][n - 1]

• Loop order. Iterate by length (gap) first. Looping left from 0 upward and right outward often reads cells not yet computed.
• Exclusive versus inclusive endpoints. Balloons use exclusive borders (l and r stay), stones use inclusive ones. Pick one convention and keep the base case consistent with it.
• Padding. Without the two 1s, bursting an end balloon needs special cases. Padding removes them.
• Empty or single input. A single balloon earns 1 * x * 1; an empty row earns 0, and max over an empty range would raise, so guard it or use default=0.
• Rolling the table. The stone-game table can be reduced to one list as above because each length depends only on the previous length, but balloons need the full table since the split point reaches far.
• Recursion depth. Memoized recursion over ranges may nest n deep; bottom-up avoids hitting Python's recursion limit.

Complexity and tradeoffs

• Time: O(n²) cells. Stone-from-either-end does O(1) per cell, so O(n²) total; balloons try O(n) split points per cell, so O(n³). Stone Game II is O(n³) worst case.
• Space: O(n²) for the table; the stone-game version can drop to O(n).
• Baseline. Trying every burst order is n!; trying every move sequence in a two-player game is 2ⁿ.
• Shortcut for stones. For the plain either-end game with an even number of piles, the first player never loses, by taking all odd-position or all even-position piles, and wins outright when the total is odd, as Stone Game guarantees; the DP is needed only when the margin or the variant matters.
• When it fails. If the cost of a move depends on more than the range endpoints (for example on which items were removed earlier inside it), the state is too small. Then you may need a bitmask of removed items, or a different decomposition.

Problems

Burst Balloons is the one to master: it teaches "choose the last, not the first". The two Stone Game problems show the score-difference trick and the one-sided state.

Medium

• 877. Stone Game NeetCode 250
  A range DP of the score difference the current player can force, choosing either end, solves it; parity also shows the first player always wins.
• 1140. Stone Game II NeetCode 250
  Memoize on the start index and the current M, with suffix sums giving the stones still available.

Hard

• 312. Burst Balloons NeetCode 150 NeetCode 250
  Choose which balloon bursts last within a range, since its neighbours are then the fixed range boundaries.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 1406. Stone Game III Hard

Connections

This builds directly on the prefix-pair tables from two-string DP, with both indices now living in the same sequence. The "last operation" view is the same one that makes divide and conquer work, and the score-difference trick for two players returns in game theory and minimax search.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14, matrix-chain multiplication and optimal binary search trees.
• Knuth, D. E., "Optimum binary search trees", Acta Informatica 1, 1971, which speeds up the split search for a family of interval recurrences.
• Skiena, S., The Algorithm Design Manual, chapter 10 on dynamic programming.
• Kleinberg and Tardos, Algorithm Design, section 6.5 on RNA secondary structure, an interval DP.
• Sedgewick and Wayne, Algorithms, section 4.4 (acyclic shortest paths): filling intervals shortest first is relaxing a DAG's vertices in topological order.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.