On this page

Interval DP

You have six matrices to multiply, A1 · A2 · A3 · A4 · A5 · A6. Matrix multiplication is associative, so every way of placing brackets gives the same product, but the cost differs wildly: for the six matrices in CLRS's example, the best bracketing needs 15,125 scalar multiplications and the worst needs more than ten times that. Which brackets should you choose?

You have a row of balloons with numbers on them. Popping a balloon earns the product of its number and its two current neighbours. In what order should you pop them to earn the most?

You have a wooden stick with marks where it must be cut. Each cut costs the length of the piece you are cutting. In what order should you cut?

These are interval DP problems. The state is a contiguous range of the input, dp[i][j] = "the best answer for the piece from to ", and the transition tries every way to split that range into two smaller ranges (or to peel something off its ends). Short ranges are solved first, long ranges are built from them, and the whole input is the last range you fill.

Interval DP is the step up from Grid DP and Sequence DP. There, a cell read neighbours. Here, a cell reads pairs of smaller cells (one pair per split point), so the typical cost is , and the hard part is choosing which event the split point stands for. Get that choice right (the "last balloon" instead of the "first balloon") and a seemingly impossible problem falls apart into independent pieces.

Why this exists

Many problems have this shape: a sequence must be combined or taken apart step by step, and each step's cost depends on what is next to what at that moment. Brute force over all orders is factorial or Catalan-sized. The number of ways to fully parenthesise a product of matrices is the Catalan number : 42 for 6 matrices, 4,862 for 10, and about for 25.

The insight that makes them tractable, written down for matrix chains by Godbole (1973) and popularised by CLRS, is that the outermost operation splits the problem into two contiguous halves that do not interact. Whatever brackets you put inside A1..Ak, they have nothing to do with the brackets inside A(k+1)..An. So the best bracketing of the whole chain is "best split point, then best left half, then best right half", and there are only different halves.

The same structure appears in Knuth's 1971 optimal binary search tree algorithm, in the Cocke–Younger–Kasami (CYK) parser for context-free grammars (1960s), in the Nussinov (1978) and Zuker (1981) algorithms for predicting how an RNA molecule folds, and in NumPy's multi_dot, which still runs the textbook matrix-chain DP to decide the order of multiplications.

Pattern triggers

If the problem says or has…Think of…
"minimum cost to multiply / merge / combine adjacent things"Split-point interval DP: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + cost(i, k, j)
"parenthesise", "order of operations", "evaluate the expression in the best order"Matrix chain multiplication shape
"pop / remove / burst, and the score depends on current neighbours"Choose the last element removed in the range, not the first
"cut a stick / rod / string at given points, each cut costs the current length"Interval DP over cut positions (sorted, with the two ends added)
"merge adjacent piles, cost = size of merged pile"Stone merging: interval DP with prefix sums
"optimal binary search tree", "minimise expected search cost given frequencies"Root choice = split point; Knuth's monotone-root speed-up
"triangulate a convex polygon", "score of a triangle = product of corners"MCM in disguise: the triangle on edge (i, j) picks a third vertex k
"palindrome", "remove from either end", "two players take from the ends"Shrink-from-the-ends interval DP: dp[i][j] from dp[i+1][j], dp[i][j-1], dp[i+1][j-1]
"removing a block makes its neighbours adjacent and they may then combine"Interval DP with an extra parameter (remove boxes, Zuma)
and the answer depends on a contiguous range interval DP fits; usually needs Knuth or a different idea

The meta-trigger: after you make one decision inside a range, what is left is one or two smaller contiguous ranges that no longer affect each other. If the leftover pieces still interact (like balloons when you pop the first one), choose a different decision to put at the split.

Intuition & first principles

Ranges instead of prefixes

In sequence DP, the state was a prefix: "the first letters". That works when decisions happen left to right. In interval DP, the last decision can happen anywhere in the middle (the outermost multiplication, the last balloon, the root of the tree), and it leaves pieces on both sides. So the state must name both ends: dp[i][j] for the range from index to index .

A tiny example. Three matrices: A1 is 10×30, A2 is 30×5, A3 is 5×60. Multiplying a matrix by a matrix costs scalar multiplications.

  • (A1 A2) A3: first , giving a 10×5 matrix; then . Total 4,500.
  • A1 (A2 A3): first , giving a 30×60 matrix; then . Total 27,000.

Same product, six times the work. With three matrices you can check both by hand. With twenty you cannot, but you can ask: "what is the last multiplication?" It multiplies the result of A1..Ak by the result of A(k+1)..An for some . Each half is a smaller instance of the same question.

Two shapes of transition

Almost every interval DP uses one of two shapes.

Shape 1: split at a point . The range is cut into and (or and when is a shared boundary), plus a cost for joining them:

Matrix chains, stone merging, cutting a stick, optimal BSTs, burst balloons and polygon triangulation are all this shape. Each cell does work, so the total is .

Shape 2: shrink from the ends. The range loses its first element, its last element, or both:

Longest palindromic subsequence (from Sequence DP), the "is s[i..j] a palindrome" table (from String DP) and two-player "take from either end" games are this shape. Each cell does work, total .

The fill order: by length

A cell dp[i][j] reads only cells for strictly shorter ranges inside . So the safe order is: all ranges of length 1, then all of length 2, and so on up to length .

graph LR
    L1["length 1: dp[i][i] base cases"] --> L2["length 2: dp[i][i+1]"]
    L2 --> L3["length 3: dp[i][i+2]"]
    L3 --> LD["..."]
    LD --> LN["length n: dp[0][n-1] is the answer"]

In the table, that is filling diagonal by diagonal, starting from the main diagonal and moving towards the top-right corner. An equivalent order is " from down to 0, and for each , from up to " (row by row from the bottom): when you reach dp[i][j], every dp[i][k] with is in the same row to the left, and every dp[k][j] with is in a lower row. Both orders work; length-first is easier to reason about, bottom-up rows are easier to make cache-friendly.

graph TD
    C["dp[i][j]"] --> A1["dp[i][k] left part, same row"]
    C --> B1["dp[k+1][j] right part, lower row"]
    A1 -.->|"shorter range"| OK["already filled"]
    B1 -.->|"shorter range"| OK

The four questions for every interval DP

  1. What does dp[i][j] mean? Include the endpoints or not? (Burst balloons uses an open interval: the balloons strictly between and .)
  2. What single decision splits the range? The outermost multiplication, the root of the tree, the first cut, the last balloon.
  3. Are the leftover pieces independent after that decision? If not, choose a different decision (this is the whole point of the burst-balloons trick).
  4. What does the join cost depend on? Usually the endpoints and the split point only: , cuts[j] - cuts[i], the sum of the range (prefix sums give it in ).

Mechanics

1. Matrix chain multiplication

Input: dimensions ; matrix is . State: m[i][j] = minimum scalar multiplications to compute (1-indexed, inclusive). Base: m[i][i] = 0 (a single matrix needs no work). Transition: the last multiplication joins (a matrix) with (a matrix):

Reconstruction: s[i][j] = the that achieved the minimum. The brackets are ( best of )( best of ), recursively.

The CLRS example (§14.2): , six matrices.

MatrixA1A2A3A4A5A6
Size30×3535×1515×55×1010×2020×25

Filling by length. Length 2 has one split each:

CellSplitComputationm
m[1][2]k=130·35·1515,750
m[2][3]k=235·15·52,625
m[3][4]k=315·5·10750
m[4][5]k=45·10·201,000
m[5][6]k=510·20·255,000

Length 3, cell m[1][3]: k=1 gives ; k=2 gives . Minimum 7,875 at k=1, so (A1 (A2 A3)).

Length 4, cell m[2][5] (CLRS works this one in the text):

km[2][k]m[k+1][5]Total
202,50035·15·20 = 10,50013,000
32,6251,00035·5·20 = 3,5007,125
44,375035·10·20 = 7,00011,375

The full tables (row , column ; only is used):

m        j=1     2      3      4      5      6         s    j=2  3  4  5  6
i=1        0 15750   7875   9375  11875  15125       i=1    1  1  3  3  3
i=2              0   2625   4375   7125  10500       i=2       2  3  3  3
i=3                     0    750   2500   5375       i=3          3  3  3
i=4                            0   1000   3500       i=4             4  5
i=5                                   0   5000       i=5                5
i=6                                          0

The last cell, m[1][6], tries all five split points:

kLeft m[1][k]Right m[k+1][6]Total
1010,50030·35·25 = 26,25036,750
215,7505,37530·15·25 = 11,25032,375
37,8753,50030·5·25 = 3,75015,125
49,3755,00030·10·25 = 7,50021,875
511,875030·20·25 = 15,00026,875

Answer: 15,125, with s[1][6] = 3. Unfolding the s table: s[1][3] = 1 splits the left half into A1 (A2 A3); s[4][6] = 5 splits the right half into (A4 A5) A6. The optimal order is

which matches CLRS. Notice the winning split is at the 5, the smallest inner dimension: making the two halves meet at a thin "waist" keeps the final multiplication cheap. That is a good intuition, but not a rule; the DP is what proves it.

graph TD
    R["A1..A6: split k=3, last product 30x5x25 = 3750"] --> L["A1..A3: split k=1, 30x35x5 = 5250"]
    R --> RR["A4..A6: split k=5, 5x20x25 = 2500"]
    L --> L1["A1"]
    L --> L2["A2..A3: 35x15x5 = 2625"]
    L2 --> L21["A2"]
    L2 --> L22["A3"]
    RR --> R1["A4..A5: 5x10x20 = 1000"]
    RR --> R2["A6"]
    R1 --> R11["A4"]
    R1 --> R12["A5"]

Each internal node of this tree is one matrix multiplication, costing for its range and split. There are of them, and their costs add up to the table's answer: . Adding up the node costs of your reconstructed tree is a cheap self-check that the reconstruction matches the table.

2. Burst balloons: why the last balloon, not the first

Problem (LeetCode 312). Balloons in a row carry numbers nums[0..n-1]. Popping balloon earns left · nums[x] · right, where left and right are the numbers on its current neighbours (a missing neighbour counts as 1). Pop all balloons; maximise the total.

Pad the array with a 1 at each end: a = [1] + nums + [1]. The pads are never popped; they just play the role of "missing neighbour = 1".

First attempt: choose the first balloon to pop. Pop balloon first in the range. Now the balloons on its left and right are neighbours of each other. The left part's last balloon and the right part's first balloon interact: when you later pop the left part's last balloon, its right neighbour is a balloon from the right part, which may or may not have been popped yet. The two halves are not independent, so "best left + best right" is meaningless.

Concretely, with nums = [3, 1, 5, 8]: pop the 1 first (earning ). The left part is [3] and the right part is [5, 8]. But popping the 3 next earns (its right neighbour is now the 5), while popping it last earns . The left part's value depends on what the right part has done. No subproblem table can capture that with two indices.

Second attempt: choose the last balloon to pop. Let dp[i][j] = the most coins from popping every balloon strictly between and (an open interval), given that and are still standing the whole time. Suppose balloon () is the last one popped in that range.

  • Until is popped, stands between the two sides like a wall. Every balloon in has neighbours inside only; every balloon in has neighbours inside only. The two sides are independent, and each is exactly the subproblem dp[i][k] or dp[k][j].
  • When is finally popped, everything between and is gone, so its neighbours are exactly and : it earns a[i] · a[k] · a[j].

Answer: dp[0][n+1].

graph LR
    I["a[i] stays"] --- LEFT["balloons in (i, k): popped first, independent"]
    LEFT --- K["a[k]: popped LAST"]
    K --- RIGHT["balloons in (k, j): popped first, independent"]
    RIGHT --- J["a[j] stays"]

Dry run, nums = [3, 1, 5, 8], a = [1, 3, 1, 5, 8, 1] (indices 0..5):

Cell (open interval)Balloons insideOptions (last = k)dp
dp[0][2]3k=1: 3
dp[1][3]1k=2: 15
dp[2][4]5k=3: 40
dp[3][5]8k=4: 40
dp[0][3]3, 1k=1: ; k=2: 30
dp[1][4]1, 5k=2: ; k=3: 135
dp[2][5]5, 8k=3: ; k=4: 48
dp[0][4]3, 1, 5k=1: ; k=2: ; k=3: 159
dp[1][5]1, 5, 8k=2: ; k=3: ; k=4: 159
dp[0][5]allk=1: ; k=2: ; k=3: ; k=4: 167

The best last balloon is the 8. Unwinding: inside the last is the 3, inside the last is the 5, inside only the 1. So the popping order is 1, 5, 3, 8: . A brute force over all orders confirms 167.

The general lesson

When removing something changes who is next to whom, think about the element that is removed last in a range. Until then, it separates the two sides, so they cannot interact. Equivalently, think of the process in reverse: adding balloons back, the first one added splits the range.

3. Minimum cost to cut a stick: here "first" works

Problem (LeetCode 1547). A stick of length has marks at positions cuts. Cutting a piece costs its current length. Cut at every mark; minimise the total.

Sort the cuts and add the two ends: c = [0] + sorted(cuts) + [n]. Let dp[i][j] = minimum cost to make every cut strictly between c[i] and c[j], on the piece from c[i] to c[j]. If the first cut on that piece is at c[k], it costs the full piece length c[j] - c[i], and afterwards the two pieces really are separate pieces of wood:

Why does "first" work here but not for balloons? Because a cut physically separates the two sides: nothing on the left piece can ever again be affected by the right piece. Popping a balloon does the opposite: it joins its two sides. Ask "after this decision, are the pieces independent?" and pick the decision that makes the answer yes.

Example: , cuts = [1, 3, 4, 5], so c = [0, 1, 3, 4, 5, 7].

CellPieceOptions (first cut at c[k]: dp[i][k] + dp[k][j])+ lengthdp
dp[0][2]0..3cut at 1: 033
dp[1][3]1..4cut at 3: 033
dp[2][4]3..5cut at 4: 022
dp[3][5]4..7cut at 5: 033
dp[0][3]0..4at 1: 0+3; at 3: 3+047
dp[1][4]1..5at 3: 0+2; at 4: 3+046
dp[2][5]3..7at 4: 0+3; at 5: 2+046
dp[0][4]0..5at 1: 0+6; at 3: 3+2; at 4: 7+0510
dp[1][5]1..7at 3: 0+6; at 4: 3+3; at 5: 6+0612
dp[0][5]0..7at 1: 0+12; at 3: 3+6; at 4: 7+3; at 5: 10+0716

Answer 16: cut at 3 first (cost 7), then the left piece 0..3 at 1 (cost 3), and the right piece 3..7 at 5 (cost 4) and then at 4 (cost 2). . Cutting in the given order 1, 3, 4, 5 would cost .

def min_cost_cut_stick(n, cuts):
    c = [0] + sorted(cuts) + [n]
    m = len(c)
    dp = [[0] * m for _ in range(m)]
    for length in range(2, m):                     # j - i, the number of gaps spanned
        for i in range(m - length):
            j = i + length
            dp[i][j] = c[j] - c[i] + min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
    return dp[0][m - 1]


assert min_cost_cut_stick(7, [1, 3, 4, 5]) == 16
assert min_cost_cut_stick(9, [5, 6, 1, 4, 2]) == 22
assert min_cost_cut_stick(5, []) == 0

Cutting a stick is the reverse of merging pieces: run time backwards and every cut becomes a merge of two adjacent pieces costing their combined length. That is exactly the next problem.

4. Merging stones (slimes)

Problem (AtCoder Educational DP Contest N, "Slimes"). Piles of sizes a[0..n-1] sit in a row. Merging two adjacent piles costs their combined size and leaves one pile of that size. Merge everything into one pile at minimum cost.

The last merge joins a pile made from a[i..k] with a pile made from a[k+1..j], and costs the total of a[i..j] no matter where is. With prefix sums pre, that total is pre[j+1] - pre[i]:

For a = [10, 20, 30, 40]: merge 10+20 (30), then 30+30 (60), then 60+40 (100): total 190. Merging from the other end is worse: 30+40 (70), then 20+70 (90), then 10+90 (100), total 260.

def merge_stones_adjacent(a):
    n = len(a)
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = pre[j + 1] - pre[i] + min(dp[i][k] + dp[k + 1][j] for k in range(i, j))
    return dp[0][n - 1]


assert merge_stones_adjacent([10, 20, 30, 40]) == 190
assert merge_stones_adjacent([10, 10, 10, 10, 10, 10]) == 160
assert merge_stones_adjacent([5]) == 0

Two notes. First, if any two piles (not just adjacent ones) may merge, the problem is Huffman coding and a greedy with a min-heap solves it in ; adjacency is what forces DP. Second, the adjacent version can be solved in by the Garsia–Wachs algorithm (1977), the same algorithm that builds optimal alphabetic codes; it is far less known than the DP and not expected in interviews. LeetCode 1000 generalises to merging exactly consecutive piles at a time, which adds a "how many piles does this range currently form" parameter.

5. Optimal binary search trees

Problem. Keys are searched with frequencies . Build a binary search tree (BST: left subtree smaller, right subtree larger) minimising , where the root has depth 1.

Choose the root of the keys . Its left subtree holds exactly and its right subtree , both contiguous ranges, and both are independent. Hanging them under a new root pushes every key in one level deeper, which adds the range's total frequency once:

Example: keys 10, 12, 20 with frequencies 34, 8, 50.

RootLeft subtreeRight subtreeCost
10—{12, 20}: best 66 (20 root, 12 below)92 + 66 = 158
12{10}: 34{20}: 5092 + 84 = 176
20{10, 12}: best 50 (10 root, 12 below)—92 + 50 = 142

The optimal tree has 20 at the root (it is searched most), 10 below it, and 12 below 10: . Note that the most frequent key is not always the root; the DP decides.

CLRS §14.5 uses a richer model with "dummy keys" for unsuccessful searches (probabilities ); the recurrence is the same with .

Knuth's speed-up. The straightforward DP is . Knuth (1971) proved that the optimal root is monotone:

So when filling e[i][j], you only try roots between those two bounds. Summed along each diagonal, the ranges telescope to , giving total. Yao (1980) generalised the condition: it works whenever the join cost satisfies the quadrangle inequality for and is monotone on nested intervals. Range sums (stone merging, optimal BST) satisfy it; matrix chain costs do not fit this form, which is why MCM has its own algorithm (Hu and Shing, 1982/1984) instead. The full treatment is in DP Optimizations.

def optimal_bst_cost(freq):
    n = len(freq)
    pre = [0]
    for f in freq:
        pre.append(pre[-1] + f)
    # e[i][j] = best cost for keys i..j-1 (half-open), so e[i][i] = 0 is an empty tree
    e = [[0] * (n + 1) for _ in range(n + 1)]
    root = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n):
        e[i][i + 1], root[i][i + 1] = freq[i], i
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length
            lo, hi = root[i][j - 1], root[i + 1][j]       # Knuth's window
            best, best_r = None, lo
            for r in range(lo, hi + 1):
                cost = e[i][r] + e[r + 1][j]
                if best is None or cost < best:
                    best, best_r = cost, r
            e[i][j], root[i][j] = best + pre[j] - pre[i], best_r
    return e[0][n]


assert optimal_bst_cost([34, 8, 50]) == 142
assert optimal_bst_cost([4, 2, 6, 3]) == 26
assert optimal_bst_cost([]) == 0

6. Palindrome partitioning: interval table + cut DP

"Cut a string into the fewest palindromic pieces" (LeetCode 132) combines two DPs:

  1. An interval table pal[i][j] (is s[i..j] a palindrome?), shape 2: pal[i][j] = s[i] == s[j] and pal[i+1][j-1]. .
  2. A 1-D cut DP over prefixes: cuts[j] = fewest cuts for s[:j+1], minimising over the start of the last piece.

The full walkthrough and code are in String DP (section 6, palindrome partitioning), and the general "split a sequence into blocks" view is in Partition DP. The point to take from it here: an interval table is often a precomputation that answers "is this range good / what does this range cost?" in , feeding a cheaper DP on top. A pure interval formulation, mincut[i][j] with a split point, also works but costs , and is a classic example of choosing the wrong state.

7. Remove boxes: when two indices are not enough

Problem (LeetCode 546). Boxes have colours. Removing a run of adjacent boxes of the same colour earns . After a removal the neighbours close up and may form a longer run. Maximise the total.

The plain dp[l][r] fails: the value of the range depends on how many boxes of the same colour as box[r] are waiting to the right of , outside the range, to be removed together with it. So add that number to the state:

f(l, r, k) = best score for boxes l..r, given that extra boxes of colour box[r] are glued to the right of .

  • Option 1: remove box[r] together with its glued friends now: .
  • Option 2: for each in with box[m] == box[r], first clear everything strictly between and (that is ), which makes box[m] adjacent to box[r] and its friends; then solve .

states with work each: worst case, fine for . For [1, 3, 2, 2, 2, 3, 4, 3, 1] the answer is 23: remove the three 2s (9), then the 4 (1), then the three 3s (9), then the two 1s (4).

from functools import lru_cache


def remove_boxes(boxes):
    b = tuple(boxes)

    @lru_cache(maxsize=None)
    def f(l, r, k):
        if l > r:
            return 0
        while l < r and b[r] == b[r - 1]:          # absorb equal neighbours into k
            r, k = r - 1, k + 1
        best = f(l, r - 1, 0) + (k + 1) ** 2
        for m in range(l, r):
            if b[m] == b[r]:
                best = max(best, f(l, m, k + 1) + f(m + 1, r - 1, 0))
        return best

    return f(0, len(b) - 1, 0)


assert remove_boxes([1, 3, 2, 2, 2, 3, 4, 3, 1]) == 23
assert remove_boxes([1, 1, 1]) == 9
assert remove_boxes([1]) == 1

This "interval plus a little extra context" pattern recurs in Zuma (Codeforces 607B), Strange Printer (LeetCode 664), and many contest problems. When dp[l][r] alone is not enough, ask: what fact about the outside world does this range's answer depend on? and add exactly that.

How the problems relate

graph TD
    T["Interval DP: dp over ranges, fill by length"] --> S1["Split at k"]
    T --> S2["Shrink from the ends"]
    S1 --> MCM["Matrix chain: join cost p[i-1] p[k] p[j]"]
    S1 --> BB["Burst balloons: k is the LAST popped"]
    S1 --> CUT["Cut a stick: k is the FIRST cut"]
    S1 --> ST["Merge stones: join cost = range sum"]
    S1 --> BST["Optimal BST: k is the root"]
    CUT -.->|"time reversed"| ST
    ST --> KN["Knuth: O(n^3) to O(n^2)"]
    BST --> KN
    S2 --> LPS["Longest palindromic subsequence"]
    S2 --> PAL["pal[i][j] table"]
    S2 --> GAME["Take-from-either-end games"]
    S1 --> RB["Remove boxes: add a third index"]

The ladder: brute force → better → optimal

Problem: matrix chain multiplication with matrices.

Rung 1: try every bracketing

Recursively split at every and evaluate both sides, without remembering anything. The number of full bracketings is the Catalan number , which grows like : 42 for , 4,862 for , 1,767,263,190 for .

def mcm_brute(p, i, j):
    if i == j:
        return 0
    return min(mcm_brute(p, i, k) + mcm_brute(p, k + 1, j) + p[i - 1] * p[k] * p[j]
               for k in range(i, j))


assert mcm_brute([30, 35, 15, 5, 10, 20, 25], 1, 6) == 15125

Rung 2: memoization

The same (i, j) pairs come up again and again: there are only of them. Cache them (functools.lru_cache) and each is computed once with work: time, space, recursion depth .

Rung 3: tabulation by length

Same time, no recursion, and the s table for reconstruction (the code in Implementation). The constant is small: the triple loop does about inner iterations, so is about 21 million, well under a second in C++.

Rung 4: problem-specific speed-ups

  • Knuth's monotone root for optimal BST and stone merging: .
  • Hu–Shing for matrix chains: via a reduction to optimal polygon triangulation. Complicated; almost never implemented in practice, because real chains are short.
  • Garsia–Wachs for adjacent stone merging / optimal alphabetic trees: .
RungMethodTimeSpaceWhy it is better
1All bracketings stackBaseline
2Memoized recursion + stackEach range solved once
3Tabulation by lengthNo recursion; split table for reconstruction
4aKnuth (when it applies)Monotone split point shrinks the inner loop
4bHu–Shing (MCM)Different structure; theory more than practice

Correctness

All split-point interval DPs share one argument: optimal substructure over a decomposition into independent ranges, followed by induction on the range length.

Matrix chains. Any full bracketing of () has an outermost multiplication, which splits the chain at some into a bracketing of and one of . Its cost is (cost of left) + (cost of right) + , because the left result is and the right is regardless of how they were bracketed. If the left part were not optimal for , replacing it with a cheaper bracketing would make the whole cheaper (cut and paste, CLRS §14.2). So the optimum is the minimum over of m[i][k] + m[k+1][j] + p p p, which is what the table computes. By induction on (both halves are strictly shorter and filled earlier), every entry is correct.

Burst balloons. Fix an open interval with and standing throughout. In any popping order of the balloons inside, some balloon is popped last. Claim: every balloon with has, at its popping time, neighbours inside . Because is still standing when is popped, the nearest standing balloon to the right of is at most ; and is standing, so the nearest to the left is at least . Symmetrically for the right side. So the coins earned on the left depend only on the order restricted to , the right only on , and the order restricted to each side is a valid popping order for that subproblem. Conversely, any pair of orders for the two sides, interleaved arbitrarily and followed by , is a valid order for with the same total. Hence the best total with last balloon is dp[i][k] + dp[k][j] + a[i] a[k] a[j], and maximising over is exact.

The "first balloon" version fails exactly this argument: after popping first, a balloon on the left may have a neighbour on the right, so the coins on one side depend on the order on the other side.

Cutting a stick. After the first cut at c[k], the two pieces are separate; the set of later cuts on each is fixed, and costs on one piece never depend on the other. Same cut-and-paste argument.

Optimal BST. In any BST on keys , the root has the keys in its left subtree and in its right (the BST property forces this). The depth of each key in the subtree is its depth within that subtree plus one, so the cost is . Cut and paste again.

Knuth's monotone root needs a separate proof (Knuth 1971; Yao 1980 via the quadrangle inequality); we use it, not prove it, here. A simple sanity check: run both the and versions on random inputs and compare, which is how this lesson's code was checked.

Complexity

ProblemStatesWork per stateTimeSpace
Shape 2 (ends): LPS, pal table, end-games, often with one row
Matrix chain for m and s
Burst balloons
Cut a stick ( cuts) — independent of the stick length
Stone merging, or amortised with Knuth /
Optimal BST, or amortised with Knuth /
Remove boxes

The loop is inner iterations. Rough budget: is instant everywhere; is about , fine in C++/Java, a few seconds in CPython; is about , too slow without Knuth or a different idea.

Unlike rolling-row DPs, interval tables do not shrink easily: dp[i][j] reads cells from the whole row and the whole column . Shape-2 problems can keep one row; split-point problems generally keep the whole triangle.

Implementation

Two programs in four languages: matrix chain multiplication with the optimal parenthesization, and burst balloons with the popping order. Each runs the lesson's examples and checks against brute force on small inputs.

Matrix chain multiplication with reconstruction

from functools import lru_cache
import random


def matrix_chain_order(p):
    """p[i-1] x p[i] is the size of matrix A_i (1-indexed). Returns (min cost, parenthesization)."""
    n = len(p) - 1
    m = [[0] * (n + 1) for _ in range(n + 1)]      # m[i][j]: cost for A_i..A_j
    s = [[0] * (n + 1) for _ in range(n + 1)]      # s[i][j]: best split k
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            m[i][j] = None
            for k in range(i, j):
                cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if m[i][j] is None or cost < m[i][j]:
                    m[i][j], s[i][j] = cost, k

    def paren(i, j):
        if i == j:
            return f"A{i}"
        k = s[i][j]
        return "(" + paren(i, k) + paren(k + 1, j) + ")"

    return (m[1][n] if n >= 1 else 0), (paren(1, n) if n >= 1 else "")


def brute(p):
    @lru_cache(maxsize=None)
    def f(i, j):
        if i == j:
            return 0
        return min(f(i, k) + f(k + 1, j) + p[i - 1] * p[k] * p[j] for k in range(i, j))
    return f(1, len(p) - 1)


if __name__ == "__main__":
    assert matrix_chain_order([30, 35, 15, 5, 10, 20, 25]) == (15125, "((A1(A2A3))((A4A5)A6))")
    assert matrix_chain_order([10, 30, 5, 60]) == (4500, "((A1A2)A3)")
    assert matrix_chain_order([10, 20]) == (0, "A1")
    assert matrix_chain_order([5, 10, 3]) == (150, "(A1A2)")
    random.seed(3)
    for _ in range(200):
        p = [random.randint(1, 30) for _ in range(random.randint(2, 8))]
        assert matrix_chain_order(p)[0] == brute(tuple(p))
    print("matrix chain tests passed")
public class MatrixChain {
    static long[][] m;
    static int[][] s;

    /** p[i-1] x p[i] is matrix A_i. Fills m and s, returns the minimum cost. */
    static long matrixChainOrder(int[] p) {
        int n = p.length - 1;
        m = new long[n + 1][n + 1];
        s = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                m[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    long cost = m[i][k] + m[k + 1][j] + (long) p[i - 1] * p[k] * p[j];
                    if (cost < m[i][j]) {
                        m[i][j] = cost;
                        s[i][j] = k;
                    }
                }
            }
        return m[1][n];
    }

    static String paren(int i, int j) {
        if (i == j) return "A" + i;
        int k = s[i][j];
        return "(" + paren(i, k) + paren(k + 1, j) + ")";
    }

    public static void main(String[] args) {
        int[] p = {30, 35, 15, 5, 10, 20, 25};
        check(matrixChainOrder(p) == 15125);
        check(paren(1, 6).equals("((A1(A2A3))((A4A5)A6))"));
        check(matrixChainOrder(new int[]{10, 30, 5, 60}) == 4500);
        check(paren(1, 3).equals("((A1A2)A3)"));
        check(matrixChainOrder(new int[]{10, 20}) == 0 && paren(1, 1).equals("A1"));
        check(matrixChainOrder(new int[]{5, 10, 3}) == 150);
        System.out.println("matrix chain tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ChainResult {
    long long cost;
    string order;
};

ChainResult matrixChainOrder(const vector<int>& p) {
    int n = (int)p.size() - 1;
    vector<vector<long long>> m(n + 1, vector<long long>(n + 1, 0));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++) {
                long long cost = m[i][k] + m[k + 1][j] + 1LL * p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }
    // build the parenthesization recursively with a small lambda
    auto paren = [&](auto&& self, int i, int j) -> string {
        if (i == j) return "A" + to_string(i);
        int k = s[i][j];
        return "(" + self(self, i, k) + self(self, k + 1, j) + ")";
    };
    return {m[1][n], paren(paren, 1, n)};
}

int main() {
    ChainResult r = matrixChainOrder({30, 35, 15, 5, 10, 20, 25});
    assert(r.cost == 15125 && r.order == "((A1(A2A3))((A4A5)A6))");
    r = matrixChainOrder({10, 30, 5, 60});
    assert(r.cost == 4500 && r.order == "((A1A2)A3)");
    r = matrixChainOrder({10, 20});
    assert(r.cost == 0 && r.order == "A1");
    r = matrixChainOrder({5, 10, 3});
    assert(r.cost == 150 && r.order == "(A1A2)");
    cout << "matrix chain tests passed\n";
    return 0;
}
function matrixChainOrder(p: number[]): [number, string] {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(n + 1).fill(0));
  const s: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let len = 2; len <= n; len++)
    for (let i = 1; i + len - 1 <= n; i++) {
      const j = i + len - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (cost < m[i][j]) {
          m[i][j] = cost;
          s[i][j] = k;
        }
      }
    }
  const paren = (i: number, j: number): string =>
    i === j ? `A${i}` : "(" + paren(i, s[i][j]) + paren(s[i][j] + 1, j) + ")";
  return [m[1][n], paren(1, n)];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(eq(matrixChainOrder([30, 35, 15, 5, 10, 20, 25]), [15125, "((A1(A2A3))((A4A5)A6))"]));
assert(eq(matrixChainOrder([10, 30, 5, 60]), [4500, "((A1A2)A3)"]));
assert(eq(matrixChainOrder([10, 20]), [0, "A1"]));
assert(eq(matrixChainOrder([5, 10, 3]), [150, "(A1A2)"]));
console.log("matrix chain tests passed");

Costs can exceed 32 bits quickly (three dimensions of 2,000 already give ), hence long / long long. In TypeScript, number is exact up to .

Burst balloons with the popping order

from itertools import permutations
import random


def max_coins(nums):
    """Return (best total, one optimal popping order as values)."""
    a = [1] + list(nums) + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]          # dp[i][j]: best for balloons strictly between i and j
    last = [[0] * n for _ in range(n)]
    for length in range(2, n):                # j - i
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):         # k = the LAST balloon popped in (i, j)
                v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]
                if v > dp[i][j] or last[i][j] == 0:
                    dp[i][j], last[i][j] = v, k

    order = []

    def unwind(i, j):                         # pop both sides first, then k
        if j - i < 2:
            return
        k = last[i][j]
        unwind(i, k)
        unwind(k, j)
        order.append(a[k])

    unwind(0, n - 1)
    return dp[0][n - 1], order


def simulate(nums, order_values):
    alive, total = list(nums), 0
    for v in order_values:
        x = alive.index(v)
        left = alive[x - 1] if x > 0 else 1
        right = alive[x + 1] if x + 1 < len(alive) else 1
        total += left * v * right
        alive.pop(x)
    return total


def brute(nums):
    best = 0
    for perm in permutations(range(len(nums))):
        alive, total = list(range(len(nums))), 0
        for idx in perm:
            x = alive.index(idx)
            left = nums[alive[x - 1]] if x > 0 else 1
            right = nums[alive[x + 1]] if x + 1 < len(alive) else 1
            total += left * nums[idx] * right
            alive.pop(x)
        best = max(best, total)
    return best


if __name__ == "__main__":
    total, order = max_coins([3, 1, 5, 8])
    assert total == 167 and order == [1, 5, 3, 8]
    assert simulate([3, 1, 5, 8], order) == 167
    assert max_coins([1, 5])[0] == 10
    assert max_coins([]) == (0, [])
    random.seed(5)
    for _ in range(200):
        nums = random.sample(range(1, 12), random.randint(1, 6))   # distinct values so simulate() is unambiguous
        t, o = max_coins(nums)
        assert t == brute(nums) == simulate(nums, o)
    print("burst balloons tests passed")
import java.util.ArrayList;
import java.util.List;

public class BurstBalloons {
    static int[] a;
    static int[][] dp, last;

    static int maxCoins(int[] nums, List<Integer> order) {
        int n = nums.length + 2;
        a = new int[n];
        a[0] = a[n - 1] = 1;
        for (int i = 0; i < nums.length; i++) a[i + 1] = nums[i];
        dp = new int[n][n];
        last = new int[n][n];
        for (int len = 2; len < n; len++)
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++) {        // k = last balloon popped in (i, j)
                    int v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
                    if (v > dp[i][j] || last[i][j] == 0) {
                        dp[i][j] = v;
                        last[i][j] = k;
                    }
                }
            }
        order.clear();
        unwind(0, n - 1, order);
        return dp[0][n - 1];
    }

    static void unwind(int i, int j, List<Integer> order) {
        if (j - i < 2) return;
        int k = last[i][j];
        unwind(i, k, order);
        unwind(k, j, order);
        order.add(a[k]);
    }

    public static void main(String[] args) {
        List<Integer> order = new ArrayList<>();
        check(maxCoins(new int[]{3, 1, 5, 8}, order) == 167);
        check(order.equals(List.of(1, 5, 3, 8)));
        check(maxCoins(new int[]{1, 5}, order) == 10);
        check(maxCoins(new int[]{}, order) == 0 && order.isEmpty());
        check(maxCoins(new int[]{7}, order) == 7);
        System.out.println("burst balloons tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int maxCoins(const vector<int>& nums, vector<int>& order) {
    int n = (int)nums.size() + 2;
    vector<int> a(n, 1);
    for (size_t i = 0; i < nums.size(); i++) a[i + 1] = nums[i];
    vector<vector<int>> dp(n, vector<int>(n, 0)), last(n, vector<int>(n, 0));
    for (int len = 2; len < n; len++)
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {            // k = last balloon popped in (i, j)
                int v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
                if (v > dp[i][j] || last[i][j] == 0) { dp[i][j] = v; last[i][j] = k; }
            }
        }
    order.clear();
    function<void(int, int)> unwind = [&](int i, int j) {
        if (j - i < 2) return;
        int k = last[i][j];
        unwind(i, k);
        unwind(k, j);
        order.push_back(a[k]);
    };
    unwind(0, n - 1);
    return dp[0][n - 1];
}

int main() {
    vector<int> order;
    assert(maxCoins({3, 1, 5, 8}, order) == 167);
    assert((order == vector<int>{1, 5, 3, 8}));
    assert(maxCoins({1, 5}, order) == 10);
    assert(maxCoins({}, order) == 0 && order.empty());
    assert(maxCoins({7}, order) == 7);
    cout << "burst balloons tests passed\n";
    return 0;
}
function maxCoins(nums: number[]): [number, number[]] {
  const a = [1, ...nums, 1];
  const n = a.length;
  const dp: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  const last: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let len = 2; len < n; len++)
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      for (let k = i + 1; k < j; k++) { // k = last balloon popped in (i, j)
        const v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
        if (v > dp[i][j] || last[i][j] === 0) {
          dp[i][j] = v;
          last[i][j] = k;
        }
      }
    }
  const order: number[] = [];
  const unwind = (i: number, j: number): void => {
    if (j - i < 2) return;
    const k = last[i][j];
    unwind(i, k);
    unwind(k, j);
    order.push(a[k]);
  };
  unwind(0, n - 1);
  return [dp[0][n - 1], order];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(eq(maxCoins([3, 1, 5, 8]), [167, [1, 5, 3, 8]]));
assert(maxCoins([1, 5])[0] === 10);
assert(eq(maxCoins([]), [0, []]));
assert(maxCoins([7])[0] === 7);
console.log("burst balloons tests passed");

The last[i][j] == 0 condition makes sure a split is recorded even when every option scores 0 (it cannot here, since all numbers are positive in the LeetCode constraints, but zero-valued balloons are allowed and would otherwise leave last unset). Balloon values up to 100 and keep totals within 32 bits in the LeetCode version; use 64-bit for larger inputs.

Real-world uses

  • Linear algebra libraries. NumPy's numpy.linalg.multi_dot chooses the multiplication order for a chain of arrays with the matrix-chain DP (its documentation cites CLRS), and tensor-contraction libraries such as opt_einsum solve the generalised ordering problem with DP and greedy heuristics. For a chain like A (1000×10) · B (10×1000) · v (1000×1), the right order is the difference between a 1000×1000 intermediate and a 10-element one.
  • Parsing. The CYK algorithm decides whether a string belongs to a context-free grammar in Chomsky normal form by filling table[i][j] = "which non-terminals can produce s[i..j]", splitting each span at every . It is interval DP in its purest form, , and its probabilistic version (the inside algorithm) scores parse trees in statistical NLP.
  • RNA secondary structure. An RNA strand folds back on itself, pairing bases. Nussinov's algorithm (1978) maximises base pairs with dp[i][j] over sub-strands; the Zuker–Stiegler algorithm (1981), the basis of tools such as ViennaRNA's RNAfold and mfold, minimises free energy with several interval tables.
  • Compilers and query engines. Optimal evaluation order for associative chains (string concatenations, joins along a chain query) is a matrix-chain variant. Database join ordering over arbitrary join graphs uses DP over subsets instead of intervals (System R, Selinger et al., 1979) — see Bitmask DP — but for chain-shaped queries it collapses to the interval form.
  • Optimal alphabetic codes and search trees. Static dictionaries with known access frequencies (compiler keyword tables, read-only lookup structures) can use Knuth's optimal BST; Hu–Tucker and Garsia–Wachs build optimal alphabetic prefix codes, where codewords must keep the symbols' sort order.
  • Computational geometry. Minimum-weight triangulation of a convex polygon is interval DP over vertex ranges (for general point sets the problem is NP-hard; Mulzer and Rote, 2008).

Pitfalls & edge cases

  • Wrong fill order. Iterating i from 0 upward with j from i upward reads dp[k+1][j] for rows that are not filled yet. Fill by length, or i downward.
  • Closed vs open intervals. Burst balloons uses (i, j) exclusive with padded 1s; MCM uses [i, j] inclusive; cutting a stick uses cut indices. Write the meaning of dp[i][j] in a comment before coding, and derive the base case from it.
  • Choosing "first" when it should be "last" (balloons) or the reverse. Always run the independence check.
  • Forgetting to sort the cuts and add the ends 0 and .
  • Using stick length as a DP dimension. can be while there are only 100 cuts; index the DP by cut number.
  • Overflow in MCM costs and in merge totals.
  • Initialising min cells to 0. For minimisation the cell must start at infinity (or at the first option); a 0 there silently wins.
  • Empty input. Zero matrices, zero balloons, zero cuts: return 0, and make sure loops with range(2, n) do not index past the end.
  • Applying Knuth's speed-up where it does not hold. Matrix chain costs do not satisfy the quadrangle-inequality form; using the root window there can give wrong answers. Test against the cubic version.
  • Recursion depth for memoised versions is , fine, but the memo for remove boxes is entries: 1 million for , fine; for larger , rethink.

Variations

  • Minimum score triangulation (LeetCode 1039): vertices of a convex polygon in order; the triangle on edge uses some third vertex ; dp[i][j] = min dp[i][k] + dp[k][j] + v_i v_k v_j. Exactly the burst-balloons recurrence with min.
  • Minimum cost tree from leaf values (LeetCode 1130): interval DP with "max leaf in each half"; also solvable greedily with a monotonic stack.
  • Guess number higher or lower II (LeetCode 375): minimax interval DP: dp[i][j] = min over guess k of k + max(dp[i][k-1], dp[k+1][j]).
  • Two-player games on ranges (take from either end, Stone Game, Removal Game): dp[i][j] = best score difference for the player to move. These belong to Game DP.
  • Strange printer (LeetCode 664): print runs of one letter over a range; extra structure similar to remove boxes.
  • Circular arrays (stones arranged in a circle): double the array to length and take the best window of length , still .
  • Expression evaluation ("how many ways to parenthesise to get true", "maximum value of an expression with + and ×"): split at each operator, keep min and max (multiplication by a negative flips them).
  • Speed-ups. Knuth–Yao for quadrangle-inequality costs; divide and conquer optimisation for layered partition DPs (see Partition DP). Both in DP Optimizations.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Longest Palindromic Subsequence (LeetCode 516) — Shape-2 warm-up: the longest palindrome you can keep by deleting letters. Teaches fill order on a triangle.

Hint

dp[i][j] = dp[i+1][j-1] + 2 on equal ends, else max(dp[i+1][j], dp[i][j-1]). See Sequence DP.

2. Minimum Insertion Steps to Make a String Palindrome (LeetCode 1312) — Fewest letters to insert so the string reads the same both ways. Teaches a direct shape-2 cost DP.

Hint

Equal ends: dp[i+1][j-1]. Different ends: 1 + min(dp[i+1][j], dp[i][j-1]). Or n - LPS.

3. Removal Game (CSES 1097) — Two players alternately take a number from either end of a list; maximise the first player's total. Teaches the score-difference interval DP.

Hint

diff[i][j] = max(x[i] - diff[i+1][j], x[j] - diff[i][j-1]); first player's score = (total + diff[0][n-1]) / 2.

4. Minimum Score Triangulation of Polygon (LeetCode 1039) — Cut a convex polygon into triangles; each triangle scores the product of its corners; minimise. Teaches the "edge (i, j) picks a third vertex" split.

Solution
def min_score_triangulation(v):
    n = len(v)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = min(dp[i][k] + dp[k][j] + v[i] * v[k] * v[j] for k in range(i + 1, j))
    return dp[0][n - 1]


assert min_score_triangulation([1, 2, 3]) == 6
assert min_score_triangulation([3, 7, 4, 5]) == 144
assert min_score_triangulation([1, 3, 1, 4, 1, 5]) == 13

Identical in shape to burst balloons, with min instead of max: the polygon edge plays the role of the two standing balloons.

5. Slimes (AtCoder Educational DP Contest N) — Merge adjacent slimes into one at minimum total cost. Teaches the range-sum join with prefix sums.

Hint

merge_stones_adjacent above. Values reach about : 64-bit integers.

6. Burst Balloons (LeetCode 312) — The lesson's problem. Teaches the last-element trick.

Solution

max_coins above. : about inner iterations.

7. Minimum Cost to Cut a Stick (LeetCode 1547) — The lesson's stick. Teaches indexing by cut, not by length.

Solution

min_cost_cut_stick in section 3.

8. Guess Number Higher or Lower II (LeetCode 375) — Guaranteed-win budget when every wrong guess costs its value. Teaches minimax over a range.

Hint

dp[i][j] = min over k in [i, j] of k + max(dp[i][k-1], dp[k+1][j]), with empty ranges costing 0.

9. Minimum Cost Tree From Leaf Values (LeetCode 1130) — Build a tree whose in-order leaves are the array; each internal node costs the product of the largest leaf on each side. Teaches carrying a range maximum alongside the DP.

Hint

Precompute mx[i][j]. dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + mx[i][k] * mx[k+1][j]. Bonus: an monotonic-stack greedy exists.

10. Deque (AtCoder Educational DP Contest L) — Two players alternately take from either end of a sequence; output the first player's score minus the second's under optimal play. Teaches the score-difference recurrence in its cleanest form.

Hint

d[i][j] = max(a[i] - d[i+1][j], a[j] - d[i][j-1]), filled by length. 64-bit integers.

11. Strange Printer (LeetCode 664) — A printer prints runs of one letter over a range, overwriting; fewest turns to produce a string. Teaches merging equal endpoints.

Hint

dp[i][j] = dp[i][j-1] + 1, improved to dp[i][k] + dp[k+1][j-1] for each with s[k] == s[j]: the last letter is printed in the same turn as an earlier equal letter.

12. Minimum Cost to Merge Stones (LeetCode 1000) — Merge exactly consecutive piles at a time. Teaches feasibility conditions () and a "number of piles" dimension.

Hint

dp[i][j] = min cost to reduce i..j to as few piles as possible; split with step ; add the range sum when (j - i) % (K - 1) == 0.

13. Zuma (Codeforces 607B) — Remove palindromic substrings of gemstones in the fewest seconds. Teaches shape-2 with an "ends match, merge into the inner palindrome" case.

Hint

dp[i][j] = seconds to destroy c[i..j]. Options: destroy c[i] alone (1 + dp[i+1][j]); if c[i] == c[i+1], destroy the pair together (1 + dp[i+2][j]); for each with c[i] == c[k], let c[i] and c[k] wrap whatever palindrome is removed last from c[i+1..k-1] (dp[i+1][k-1] + dp[k+1][j]).

14. Remove Boxes (LeetCode 546) — The lesson's hard extension. Teaches adding outside context to the state.

Solution

remove_boxes in section 7. Memoised recursion is the natural form; tabulating a 3-D state is possible but harder to read.

Common mistakes & interview follow-ups

"Why is burst balloons not 'pick the first balloon'?" Explain the independence failure with [3, 1, 5, 8]: popping the 1 first makes 3 and 5 neighbours, so the left side's value depends on the right side's order. Then explain why the last balloon walls the two sides off.

"What is the time complexity, and can you do better?" for the generic split DP. Knuth's speed-up gives when the cost satisfies the quadrangle inequality (optimal BST, stone merging). For MCM, Hu–Shing is but rarely implemented.

"Print the order, not just the cost." Store the best split per cell and unwind recursively (MCM brackets, balloon order).

"What if the stones are in a circle?" Duplicate the array and solve windows of length .

"Merge any two piles, not just adjacent ones?" That is Huffman coding: a greedy with a heap, . The adjacency constraint is what makes it interval DP.

"How would you test this?" Brute force over all orders/bracketings for , random inputs, compare. That is how this lesson's code was checked.

Mistakes interviewers watch for: looping i upward so you read unfilled cells; inclusive/exclusive confusion with padded arrays; initialising a min to 0; forgetting to sort cuts; overflow.

Quick quiz

1. In the CLRS chain, which split does m[1][6] choose, and what is the waist dimension there?

Answer

, joining a result with a result; the waist is 5, the smallest inner dimension.

2. For burst balloons, what does dp[i][j] mean, and why are and excluded?

Answer

The best coins from popping the balloons strictly between and , with and standing throughout. They are excluded because they act as the fixed neighbours of the last balloon popped in the range.

3. Why does "first cut" work for cutting a stick but "first balloon" fails for balloons?

Answer

A cut separates the stick into two pieces that never interact again. Popping a balloon joins its two sides, so they do interact. "Last balloon" is the decision that separates.

4. How many full parenthesizations does a chain of 6 matrices have?

Answer

The Catalan number .

5. In the stick example (, cuts 1, 3, 4, 5), which cut is made first in the optimal plan, and what is the total?

Answer

Cut at 3 first; total 16 (7 + 3 + 4 + 2).

6. Which of these satisfy Knuth's condition: stone merging, optimal BST, matrix chain?

Answer

Stone merging and optimal BST (range-sum costs satisfy the quadrangle inequality and monotonicity). Matrix chain does not fit the form.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., §14.2 (matrix-chain multiplication, the 30/35/15/5/10/20/25 example) and §14.5 (optimal binary search trees).
  • Donald E. Knuth, "Optimum binary search trees", Acta Informatica 1, 1971.
  • F. Frances Yao, "Efficient dynamic programming using quadrangle inequalities", STOC 1980.
  • T. C. Hu and M. T. Shing, "Computation of Matrix Chain Products", Part I (SIAM J. Computing 11(2), 1982) and Part II (13(2), 1984).
  • Adriano M. Garsia and Michelle L. Wachs, "A New Algorithm for Minimum Cost Binary Trees", SIAM J. Computing 6(4), 1977.
  • Ruth Nussinov et al., "Algorithms for loop matchings", SIAM J. Applied Mathematics 35(1), 1978; Michael Zuker and Patrick Stiegler, "Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information", Nucleic Acids Research 9(1), 1981.
  • NumPy documentation, numpy.linalg.multi_dot.
  • cp-algorithms, Knuth's Optimization.
  • AtCoder Educational DP Contest, problem list — N (Slimes) and L (Deque) are interval DPs.

Lessons: previous — Grid DP · next — Partition DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Sequence DP · String DP · Grid DP · Binary Search Trees · Greedy Algorithms · DP Optimizations · Game DP.