Skip to main content

Interval DP: Matrix Chain, Optimal BST, Balloon Burst

What This Concept Is​

Interval DP solves optimization problems where the state is a contiguous range $[i, j]$ of a sequence, and the recurrence splits the range at some split point $k$ inside it:

$$dp[i][j] = \operatorname*{opt}_{i \le k < j} \Big( dp[i][k] + dp[k+1][j] + \operatorname{cost}(i, k, j) \Big).$$

The fill order is by increasing interval length, not by index -- a subtle but essential change in mental model. Canonical instances:

  • Matrix chain multiplication (CLRS 14.2). Given matrix dimensions $p[0..n]$ so that matrix $A_i$ has shape $p[i-1] \times p[i]$, find a parenthesization minimizing total scalar multiplications. $\operatorname{cost}(i, k, j) = p[i-1] \cdot p[k] \cdot p[j]$. Runtime $O(n^3)$, space $O(n^2)$. The answer space has $\Theta(C_n)$ parenthesizations (Catalan numbers, exponential), collapsed to $O(n^3)$ work by DP.
  • Optimal binary search tree (CLRS 14.5). Given keys with access frequencies, build a BST minimizing expected search cost. The split point picks the root of the subtree for keys $[i..j]$; the two sides become left and right subtrees.
  • Balloon burst (LeetCode 312). Burst balloons one by one to maximize points. The classic trick: indexing by the last balloon burst in the range, not the first, gives clean independence between the two halves. $\operatorname{cost}(i, k, j) = a[i-1] \cdot a[k] \cdot a[j+1]$ for balloon $k$ being bursted last in the open range $(i, j)$.
  • Minimum weight triangulation (Skiena 8.6.1). Split a convex polygon into triangles; recurrence picks the third vertex of the triangle containing a fixed edge.
  • Palindrome partitioning. Partition a string into the minimum number of palindromic substrings; interval DP decides "where to cut."

Why It Matters Here​

Interval DP breaks the "left-to-right" habit from sequence DP. You are not building up by appending one element; you are deciding how to split a range recursively. This departure from the linear model is the reason interval DP feels harder than grid or knapsack the first time -- but it is also the reason it unlocks a whole family of problems: matrix chain multiplication, optimal BSTs, parsing cost minimization, polygon triangulation, chain-of-operations optimization.

Interval DP is also the archetypal "rethink the splitting variable" problem. For balloon burst, choosing "first to burst" is ugly; choosing "last to burst" is clean. For matrix chain, choosing the outermost multiplication (the root of the parse tree) gives the split.

Concrete Examples​

Matrix chain multiplication. Matrices $A_1 (10 \times 30), A_2 (30 \times 5), A_3 (5 \times 60)$. So $p = [10, 30, 5, 60]$.

Interval DP on $dp[i][j]$ = min scalar multiplications for $A_i..A_j$.

Length 1: $dp[1][1] = dp[2][2] = dp[3][3] = 0$.

Length 2:

  • $dp[1][2] = p_0 \cdot p_1 \cdot p_2 = 10 \cdot 30 \cdot 5 = 1500$
  • $dp[2][3] = p_1 \cdot p_2 \cdot p_3 = 30 \cdot 5 \cdot 60 = 9000$

Length 3 (the full chain):

  • split at $k = 1$: $dp[1][1] + dp[2][3] + p_0 \cdot p_1 \cdot p_3 = 0 + 9000 + 10 \cdot 30 \cdot 60 = 27000$
  • split at $k = 2$: $dp[1][2] + dp[3][3] + p_0 \cdot p_2 \cdot p_3 = 1500 + 0 + 10 \cdot 5 \cdot 60 = 4500$
  • $dp[1][3] = 4500$

Answer: $4500$, with parenthesization $(A_1 (A_2 A_3))$.

Balloon burst. $a = [3, 1, 5, 8]$. Pad with sentinels: $[1, 3, 1, 5, 8, 1]$. Let $dp[i][j]$ = max coins from bursting balloons strictly between $i$ and $j$. Recurrence:

$$dp[i][j] = \max_{,i < k < j} \big( dp[i][k] + dp[k][j] + a_i \cdot a_k \cdot a_j \big).$$

Because $k$ is bursted last in this range, balloons $i$ and $j$ are still standing when $k$ pops.

Answer: $dp[0][5] = 167$.

Palindrome partitioning (min cuts). For $s = \texttt{"aab"}$: $dp[i][j]$ = true if $s[i..j]$ is palindrome (precomputed via interval DP), then $\mathrm{cuts}[i] = \min {, \mathrm{cuts}[k] + 1 ,:, s[k+1..i] \text{ palindrome} ,}$. Answer for "aab": 1 cut ("aa" | "b").

Top-down memoized matrix chain. Same recurrence, called on demand:

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

For $n=3$ matrices this reaches only $O(n^2)$ distinct states, same as tabulation. The cache is the table; iteration order is determined by call order rather than an explicit length loop.

Common Confusion / Misconceptions​

"Row-major fill order works." It does not for interval DP. Filling $dp[i][j]$ in row-major order reads unfilled cells. The correct order is by interval length:

for len = 2 to n:
    for i = 1 to n - len + 1:
        j = i + len - 1
        dp[i][j] = ...

"Pick any splitting variable." For balloon burst, trying to recurse on "which balloon is burst first" creates ugly dependencies because what sits on the left of a still-intact balloon changes. Recursing on "which balloon is burst last" cleans this up: after that split, the two halves are independent. The choice of splitting variable is the creative step.

"Cost is always additive." Not quite. For optimal BST, the cost adds a depth penalty because inserting a root deepens every key in the subtrees by 1. The recurrence becomes $dp[i][j] = w(i,j) + \min_k (dp[i][k-1] + dp[k+1][j])$, where $w(i,j)$ is the sum of frequencies -- a subtle but important twist.

"Interval DP is always $O(n^3)$." Often, but not always. Knuth's optimization (1971) reduces matrix chain and optimal BST-like problems to $O(n^2)$ when the quadrangle inequality holds. Divide and conquer optimization and SMAWK also give speedups for specific cost structures. Recognizing when these apply is advanced but occasionally decisive.

How To Use It​

  1. Recognize that subproblems are contiguous intervals, not prefixes.
  2. Define $dp[i][j]$ and write the recurrence with a split-point $k$.
  3. Identify the right choice to recurse on (first split, last remaining, root of subtree) -- that is usually the creative step.
  4. Fill by increasing interval length.
  5. Record the split point if you need to reconstruct the structure (parenthesization, tree).
  6. Verify on small cases by hand; compare against brute-force enumeration for $n \le 10$.
  7. If runtime is too slow and the cost function is "nice" (monotone, quadrangle inequality), consider Knuth's optimization.

Transfer / Where This Shows Up Later​

  • S3 Software Design. Compiler optimizers use interval DP to choose the parenthesization of expression trees when evaluation order affects cost (e.g., matrix libraries that choose multiplication order at plan time).
  • S5 Networking. Segmentation of a byte stream into minimum-cost chunks under compression or encryption cost is interval DP when the cost depends on chunk boundaries.
  • S6 Databases. Join-order optimization is interval-DP-shaped for left-deep trees (Selinger's System R) and generalizes to bushy trees with the same split-point structure. This is the direct cousin of matrix chain.
  • S7 Architecture. Partitioning a monolith into bounded contexts minimizing cross-boundary communication is interval DP when the entities are ordered.
  • Phase 7 AI. CYK parsing for context-free grammars is interval DP over the sentence; span-based neural parsers keep the same structure with learned cost functions.

Check Yourself​

  1. Why must interval DP be filled by increasing interval length?
  2. What makes balloon burst hard if you index by the first balloon burst instead of the last?
  3. For matrix chain, what is the number of distinct parenthesizations of $n$ matrices, and why is DP essential?
  4. Write the Bellman-style recurrence for optimal BST given key access probabilities $p_i$.
  5. When does Knuth's optimization reduce $O(n^3)$ to $O(n^2)$?
  6. Give one interval DP whose cost function depends on both endpoints and the split point (non-trivial $\operatorname{cost}(i,k,j)$).

Mini Drill or Application​

  1. Implement matrix chain with reconstruction of the parenthesization as a string.
  2. Implement optimal BST given key frequencies; reconstruct the tree.
  3. Implement balloon burst on an array of at most 12 balloons and verify against brute-force enumeration.
  4. Solve "minimum cost triangulation of a convex polygon": split a polygon into triangles minimizing total triangle weight (use any weight function, e.g., perimeter). Note that this is interval DP over polygon vertices.
  5. Palindrome partitioning -- minimum cuts. Precompute is_pal[i][j] with interval DP, then 1D DP for cuts.
  6. Merge-stones variant: given n piles of stones in a row, merge all into one pile with min cost, where each merge combines two adjacent piles into one.
  7. Implement top-down memoized matrix chain (the code block above) and verify it returns the same values as the length-loop tabulation on 20 random chains of length up to 10.
  8. Count the number of distinct optimal parenthesizations for a given matrix chain: replace $\min$ with a sum-of-arg-min over splits achieving the minimum.

Read This Only If Stuck​