---
title: Interval DP
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 6
order: 806
summary: |
  Many problems ask for the best way to combine a contiguous range of items, and
  the answer is a dynamic program over subintervals $[i,j]$ that chooses a split
  point $k$. We derive the pattern from matrix-chain multiplication —
  parenthesising a product to minimize scalar multiplications in $O(n^3)$ — distil
  it into a reusable template filled by increasing interval length, and then meet
  its sharpest variant: the "last operation" trick behind Burst Balloons and
  cutting a stick, where fixing the _last_ move (not the first) makes the two
  sides independent.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming (§15.2 Matrix-chain, §15.5 Optimal BST)"
  - book: Skiena
    ref: "§ — Dynamic Programming"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
practice:
  - title: 'Minimum Cost to Cut a Stick'
    slug: minimum-cost-to-cut-a-stick
    difficulty: Hard
  - title: 'Burst Balloons'
    slug: burst-balloons
    difficulty: Hard
  - title: 'Palindrome Partitioning II'
    slug: palindrome-partitioning-ii
    difficulty: Hard
  - title: 'Minimum Cost Tree From Leaf Values'
    slug: minimum-cost-tree-from-leaf-values
    difficulty: Medium
  - title: 'Strange Printer'
    slug: strange-printer
    difficulty: Hard
---

The sequence DPs we have met so far walked a string or array from one end and let
the subproblem be a _prefix_: the state was "the best answer using the first $i$
items." A second, equally common family does not decompose by prefix at all. It
decomposes by **contiguous range**. The natural subproblem is "the best answer
for the slice $[i,j]$," and the recurrence builds a long range out of two shorter
ranges by guessing where they meet: a **split point** $k$ inside $[i,j]$. This
is **interval dynamic programming**, one of the [core DP
patterns](/algorithms/dynamic-programming/principles). The same shape appears in
parenthesising a product, building an optimal search tree, bursting balloons,
cutting a stick, and partitioning a string.

The archetype, and the cleanest place to learn the pattern, is the problem of
parenthesising a matrix product.

## Matrix-chain multiplication

Multiplying a $p \times q$ matrix by a $q \times r$ matrix takes $pqr$ scalar
multiplications. Matrix multiplication is associative, so for a chain
$A_1 A_2 \cdots A_n$ the _answer_ is the same however we parenthesise, but the
_cost_ is not. Given a chain of $n$ matrices where $A_i$ has dimensions
$p_{i-1} \times p_i$ (so the dimension sequence is $p_0, p_1, \dots, p_n$), we
want the parenthesisation that minimizes the total number of scalar
multiplications.[^clrs-matrix]

The number of parenthesisations grows like the Catalan numbers, exponentially,
so brute force is hopeless. But the problem has the two features every DP needs.

> **Lemma (Optimal substructure).** In the optimal parenthesisation of
> $A_i \cdots A_j$, the outermost multiplication splits the chain at some $k$ into
> $(A_i \cdots A_k)(A_{k+1} \cdots A_j)$, and each side must itself be optimally
> parenthesised.

> **Proof.** Suppose a side, say $A_i \cdots A_k$, were not optimally
> parenthesised. Then a cheaper parenthesisation of that subchain exists, and
> substituting it leaves the final $p_{i-1}\,p_k\,p_j$ multiplication unchanged
> while lowering the total cost, contradicting the optimality of the whole. So
> both sides are optimal on their subchains. $\qed$

The other ingredient is **overlapping subproblems**: both sides are again
contiguous subchains, and the same subchain is reached by many different outer
choices, so a table of $\Theta(n^2)$ subchains is solved once each.

Let $m[i,j]$ be the minimum number of scalar multiplications needed to compute
$A_i \cdots A_j$. A single matrix needs no multiplications, and otherwise we try
every split:

$$
m[i,j] =
\begin{cases}
0 & i = j,\\[4pt]
\displaystyle\min_{i \le k < j}\parens{m[i,k] + m[k+1,j] + p_{i-1}\,p_k\,p_j} & i < j.
\end{cases}
$$

The term $p_{i-1} p_k p_j$ is the cost of the final multiplication: the left
block $A_i \cdots A_k$ is a $p_{i-1} \times p_k$ matrix, the right block
$A_{k+1} \cdots A_j$ is $p_k \times p_j$, and combining them costs
$p_{i-1} p_k p_j$.

$$
% caption: Combine two solved subintervals at a split $k$; the chosen split is highlighted
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % the row of matrices i..j
  \foreach \x/\lab in {0/i, 1/{}, 2/k, 3/{k{+}1}, 4/{}, 5/j} {
    \node[draw, minimum size=7mm] (n\x) at (\x*1.2, 0) {};
    \node[font=\footnotesize] at (\x*1.2, -0.62) {$\lab$};
  }
  % full bracket over [i,j]
  \draw[thick] (-0.45, 0.55) -- (6.45, 0.55);
  \draw[thick] (-0.45, 0.55) -- (-0.45, 0.4);
  \draw[thick] (6.45, 0.55) -- (6.45, 0.4);
  \node at (3.0, 0.9) {\texttt{m[i,j]}};
  % left sub-bracket [i,k]
  \draw[acc, thick] (-0.45, -1.05) -- (2.85, -1.05);
  \draw[acc, thick] (-0.45, -1.05) -- (-0.45, -0.9);
  \draw[acc, thick] (2.85, -1.05) -- (2.85, -0.9);
  \node[acc] at (1.2, -1.42) {\texttt{m[i,k]}};
  % right sub-bracket [k+1,j]
  \draw[acc, thick] (3.15, -1.05) -- (6.45, -1.05);
  \draw[acc, thick] (3.15, -1.05) -- (3.15, -0.9);
  \draw[acc, thick] (6.45, -1.05) -- (6.45, -0.9);
  \node[acc] at (4.8, -1.42) {\texttt{m[k+1,j]}};
  % combine cost
  \node at (3.0, -2.15) {combine cost $=$ \texttt{p(i-1) p(k) p(j)}};
\end{tikzpicture}
$$

### Filling the table

The recurrence for $m[i,j]$ depends only on intervals _strictly shorter_ than
$[i,j]$ (the left side has length $k-i+1 \le j-i$, the right side
$j-k \le j-i$). So if we fill the table in order of increasing interval length
$\ell = j - i + 1$, every value we read is already computed. We also record, in a
split table $s[i,j]$, the $k$ that achieved the minimum, so we can reconstruct the
parenthesisation afterwards.

```algorithm
caption: $\textsc{Matrix-Chain-Order}(p)$ — fill $m$, $s$ by increasing chain length
$n \gets \text{length}(p) - 1$
for $i \gets 1$ to $n$ do
  $m[i,i] \gets 0$
for $\ell \gets 2$ to $n$ do            // $\ell$ = chain length
  for $i \gets 1$ to $n - \ell + 1$ do
    $j \gets i + \ell - 1$
    $m[i,j] \gets \infty$
    for $k \gets i$ to $j - 1$ do        // try every split
      $q \gets m[i,k] + m[k+1,j] + p_{i-1}\cdot p_k \cdot p_j$
      if $q < m[i,j]$ then
        $m[i,j] \gets q$
        $s[i,j] \gets k$
return $m,\ s$
```

There are $\Theta(n^2)$ entries and each costs $O(n)$ to fill (the inner loop over
$k$), so the algorithm runs in $\Theta(n^3)$ time and $\Theta(n^2)$ space. The
answer is $m[1,n]$; the optimal parenthesisation is read back from $s$ by
recursing: $s[1,n]$ gives the outermost split, then $s[1,\,s[1,n]]$ and
$s[\,s[1,n]+1,\,n]$ give the next ones, and so on down to single matrices.

$$
% caption: Optimal split of $A_1\!\cdots\!A_4$ at $k=3$; each node shows its interval cost
%          $m[i,j]$, dims $p=\langle 5,4,6,2,7\rangle$
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\small},
  box/.style={draw, minimum width=18mm, minimum height=8mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=acc!12] (root) at (4,3) {\texttt{m[1,4]=158}};
  \node[box] (l) at (1.6,1.3) {\texttt{m[1,3]=88}};
  \node[box] (r) at (6.4,1.3) {\texttt{m[4,4]=0}};
  \node[box] (ll) at (0,-0.4) {\texttt{m[1,1]=0}};
  \node[box] (lr) at (3.2,-0.4) {\texttt{m[2,3]=48}};
  \draw[->, acc, thick] (root) -- node[above left=-1mm, font=\footnotesize]{\texttt{k=3}} (l);
  \draw[->] (root) -- (r);
  \draw[->, acc, thick] (l) -- node[above left=-1mm, font=\footnotesize]{\texttt{k=1}} (ll);
  \draw[->] (l) -- (lr);
  \node[font=\footnotesize] at (4,3.95) {combine $+$ \texttt{p0 p3 p4 = 5 x 2 x 7 = 70}};
\end{tikzpicture}
$$

$$
% caption: The upper-triangular $m$ table, filled along diagonals of increasing length;
%          cell $m[i,j]$ depends on its row to the left and its column below
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % grid of cells for a 5-matrix chain, upper triangle i<=j
  \foreach \i in {1,...,5} {
    \foreach \j in {1,...,5} {
      \ifnum\j<\i\else
        \node[draw, minimum size=8mm] (c\i\j) at (\j*0.9, -\i*0.9) {};
      \fi
    }
  }
  % the target cell m[2,4]
  \node[draw, fill=acc!18, minimum size=8mm] at (4*0.9, -2*0.9) {$m_{24}$};
  % its row to the left (m[2,2], m[2,3]) and column below (m[3,4], m[4,4])
  \node[draw, acc, very thick, minimum size=8mm] at (2*0.9, -2*0.9) {};
  \node[draw, acc, very thick, minimum size=8mm] at (3*0.9, -2*0.9) {};
  \node[draw, acc, very thick, minimum size=8mm] at (4*0.9, -3*0.9) {};
  \node[draw, acc, very thick, minimum size=8mm] at (4*0.9, -4*0.9) {};
  % axis labels
  \foreach \j in {1,...,5} { \node at (\j*0.9, -0.35) {$j{=}\j$}; }
  \foreach \i in {1,...,5} { \node at (0.25, -\i*0.9) {$i{=}\i$}; }
  % diagonal fill-order arrow (red process annotation), routed through the empty
  % lower-left triangle so it clears the cell digits and bordered dependency cells;
  % horizontal label placed in clear space below, with a thin red leader
  \draw[->, thick, red!75!black] (1.35*0.9, -4.75*0.9) -- (2.55*0.9, -3.55*0.9);
  \node[font=\footnotesize, align=center, red!75!black, anchor=west] at (1.15*0.9, -4.95*0.9)
    {increasing\\\texttt{len = j - i + 1}};
\end{tikzpicture}
$$

The diagonal $i = j$ (length $1$) is the base case; each successive diagonal
moving toward the top-right corner holds longer intervals, and cell $m[i,j]$
draws on cells in its own **row to the left** (the $m[i,k]$ terms) and its own
**column below** (the $m[k+1,j]$ terms). That dependency shape, left along the
row and down the column, is the signature of an interval DP.

To make the fill concrete, take the four-matrix chain with dimension sequence
$p = \langle 5, 4, 6, 2, 7 \rangle$, so $A_1$ is $5\times4$, $A_2$ is $4\times6$,
$A_3$ is $6\times2$, $A_4$ is $2\times7$. The base diagonal is all zeros. The
length-$2$ diagonal has a single split each:

$$
\begin{aligned}
m[1,2] &= p_0 p_1 p_2 = 5\cdot4\cdot6 = 120, \\
m[2,3] &= p_1 p_2 p_3 = 4\cdot6\cdot2 = 48, \\
m[3,4] &= p_2 p_3 p_4 = 6\cdot2\cdot7 = 84.
\end{aligned}
$$

The length-$3$ diagonal tries two splits each and keeps the cheaper:

$$
\begin{aligned}
m[1,3] &= \min\begin{cases} m[1,1]+m[2,3]+p_0 p_1 p_3 = 0+48+5\cdot4\cdot2 = 88 \\ m[1,2]+m[3,3]+p_0 p_2 p_3 = 120+0+5\cdot6\cdot2 = 180 \end{cases} = 88\ (k{=}1),\\[6pt]
m[2,4] &= \min\begin{cases} m[2,2]+m[3,4]+p_1 p_2 p_4 = 0+84+4\cdot6\cdot7 = 252 \\ m[2,3]+m[4,4]+p_1 p_3 p_4 = 48+0+4\cdot2\cdot7 = 104 \end{cases} = 104\ (k{=}3).
\end{aligned}
$$

Finally the length-$4$ interval tries all three splits, and $k=3$ wins with
$m[1,3]+m[4,4]+p_0 p_3 p_4 = 88 + 0 + 5\cdot2\cdot7 = 158$. The completed table
and its split choices:

$$
% caption: Completed $m$ table for $p=\langle 5,4,6,2,7\rangle$ (blanks are the unused
%          lower triangle); each cell holds the minimum cost, and the arrow marks the
%          increasing-length diagonal fill order ending at the answer $m[1,4]=158$.
\begin{tikzpicture}[
  >=stealth, every node/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \j/\lab in {1/{j=1},2/{j=2},3/{j=3},4/{j=4}} {
    \node at (\j*1.15, 0.75) {\lab};
  }
  \foreach \i/\lab in {1/{i=1},2/{i=2},3/{i=3},4/{i=4}} {
    \node at (0.15, -\i*1.15+1.15) {\lab};
  }
  % row i=1
  \node[draw, minimum size=10mm] at (1.15,0) {$0$};
  \node[draw, minimum size=10mm] at (2.30,0) {$120$};
  \node[draw, minimum size=10mm] at (3.45,0) {$88$};
  \node[draw, minimum size=10mm, fill=acc!15, draw=acc, very thick] at (4.60,0) {$158$};
  % row i=2
  \node[draw, minimum size=10mm] at (2.30,-1.15) {$0$};
  \node[draw, minimum size=10mm] at (3.45,-1.15) {$48$};
  \node[draw, minimum size=10mm] at (4.60,-1.15) {$104$};
  % row i=3
  \node[draw, minimum size=10mm] at (3.45,-2.30) {$0$};
  \node[draw, minimum size=10mm] at (4.60,-2.30) {$84$};
  % row i=4
  \node[draw, minimum size=10mm] at (4.60,-3.45) {$0$};
  % fill-order arrow through empty lower-left triangle, clear of filled cells
  \draw[->, thick, red!75!black] (0.7,-2.75) -- (2.0,-1.7);
  \node[red!75!black, anchor=west] at (0.55,-3.05) {\texttt{len} 1, 2, 3, 4};
\end{tikzpicture}
$$

::impl{algo="matrix_chain_order"}

## The interval-DP recipe

Strip matrix-chain of its specifics and a reusable pattern remains.

> **Remark (The interval-DP recipe).** Let the state be a contiguous range $[i,j]$ of the input.
> 1. **Subproblem.** $\text{dp}[i,j]$ = the optimum over the slice $[i,j]$.
> 2. **Base case.** Length-$1$ (or length-$0$) intervals are trivial.
> 3. **Recurrence.** Choose a **split or pivot** $k$ inside $[i,j]$ that breaks
>    the range into two independent subranges, combine their optima plus a cost
>    that depends only on $i$, $j$, $k$, and minimize (or maximize) over $k$.
> 4. **Order.** Fill by **increasing interval length**, so both subranges are
>    already solved when you reach $[i,j]$.
>
> With $\Theta(n^2)$ states and an $O(n)$ choice of $k$ per state, the running
> time is the characteristic $O(n^3)$.

The art in any specific problem is steps 1 and 3: defining the slice so that the
two sides really are **independent**, and finding the cost term that depends only
on the endpoints and the split. The rest is bookkeeping.

## Optimal binary search tree

A first variation keeps the split idea but changes what the cost term measures.
Given $n$ sorted keys with search probabilities $p_1, \dots, p_n$, an **optimal
[binary search tree](/algorithms/data-structures/binary-search-trees)** is the
BST minimizing the _expected_ search cost
$\sum_i p_i \cdot (\text{depth of key } i + 1)$. Choosing key $k$ as the root of
the subtree on keys $[i,j]$ splits the rest into a left subtree on $[i,k-1]$ and a
right subtree on $[k+1,j]$, again two independent ranges combined at a pivot.
Making $k$ the root pushes _every_ key in $[i,j]$ down one level, which adds the
total weight $w[i,j] = \sum_{r=i}^{j} p_r$ to the cost:

$$
e[i,j] = \min_{i \le k \le j}\parens{e[i,k-1] + e[k+1,j] + w[i,j]}.
$$

Picking root $k$ hangs the two solved subtrees beneath it, and the act of adding a
root pushes _every_ key in $[i,j]$ one level deeper, so its whole weight
$w[i,j]$ is charged once more:

$$
% caption: Root $k$ on keys $[i,j]$: the optimal subtrees on $[i,k-1]$ and $[k+1,j]$ hang
%          below, and rooting adds one level to all keys, charging $+\,w[i,j]$.
\begin{tikzpicture}[
  >=stealth, every node/.style={font=\small},
  key/.style={circle, draw=acc, very thick, minimum size=8mm, inner sep=0pt},
  sub/.style={draw, isosceles triangle, shape border rotate=90, minimum width=20mm, minimum height=11mm, inner sep=1pt, anchor=north}]
  \definecolor{acc}{HTML}{2348F2}
  \node[key] (k) at (0,0) {$k$};
  \node[sub] (L) at (-1.6,-0.85) {};
  \node[sub] (R) at (1.6,-0.85) {};
  \node[font=\footnotesize, below=1pt of L.south] {\texttt{e[i,k-1]}};
  \node[font=\footnotesize, below=1pt of R.south] {\texttt{e[k+1,j]}};
  \draw[acc, thick] (k.south) -- (L.north);
  \draw[acc, thick] (k.south) -- (R.north);
  \node[font=\footnotesize, acc, align=center, anchor=west] at (1.3,0.35)
    {root adds 1 level\\to all of \texttt{[i,j]}:\\$+$ \texttt{w[i,j]}};
\end{tikzpicture}
$$

The shape is identical to matrix-chain, with the same diagonals and the same
$O(n^3)$ fill, the combine term now being the swept-down weight of the whole
interval rather than a product of dimensions.[^clrs-obst]

::impl{algo="optimal_bst"}

## The "last operation" trick: Burst Balloons and cutting a stick

Some problems resist the naive split because the cost of a piece depends on what
is _adjacent_ to it, and the first split severs the very adjacency that sets
the cost. To address this, guess the **last** operation instead of the first.

Take **Burst Balloons**: balloons $1 \dots n$ have values $v_i$, and bursting
balloon $i$ earns $v_{\text{left}} \cdot v_i \cdot v_{\text{right}}$ where left and
right are its _current_ surviving neighbors; bursting removes $i$ and rejoins the
neighbors. We want the maximum total earnings. If we try to fix the _first_
balloon burst in $[i,j]$, the two halves are **not** independent: a balloon in the
left half can later have a right neighbor in the right half, so the halves keep
interacting through the shared boundary.

Now fix the balloon $k$ that is burst **last** in the open interval $(i,j)$ (using
sentinels $v_i, v_j$ just outside the range that are never burst). When $k$ is
burst last, _every other balloon in $(i,j)$ is already gone_, so its two
neighbors at that moment can only be the boundaries $i$ and $j$. The earnings for
that final burst are $v_i \cdot v_k \cdot v_j$, fixed and independent of order;
the balloons in $(i,k)$ were all burst _before_ $k$ while $i$ and $k$
remained fixed boundaries, and likewise $(k,j)$ against $k$ and $j$. The two
sides are therefore independent:

$$
\text{dp}[i,j] = \max_{i < k < j}\parens{\text{dp}[i,k] + \text{dp}[k,j] + v_i\, v_k\, v_j}.
$$

$$
% caption: Bursting $k$ last in $(i,j)$: every other balloon is already gone, so $k$'s
%          neighbors are pinned to the walls $i,j$ and earn $v_i v_k v_j$
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\small},
  bln/.style={circle, draw, minimum size=7mm, inner sep=0},
  wall/.style={circle, draw, fill=black!8, minimum size=7mm, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  \node[wall] (i) at (0,0) {$i$};
  \node[bln, dashed, text=black] (a) at (1.4,0) {};
  \node[bln, dashed, text=black] (b) at (2.8,0) {};
  \node[bln, draw=acc, very thick, text=acc] (k) at (4.2,0) {$k$};
  \node[bln, dashed, text=black] (c) at (5.6,0) {};
  \node[wall] (j) at (7.0,0) {$j$};
  \draw[->, acc, thick] (i) to[bend left=28] (k);
  \draw[->, acc, thick] (j) to[bend right=28] (k);
  \node[font=\footnotesize, text=black, fill=white, inner sep=1.5pt] at (2.1,0.92) {burst before $k$};
  \node[font=\footnotesize, text=black, fill=white, inner sep=1.5pt] at (5.6,0.92) {before $k$};
  \node[font=\footnotesize, acc] at (4.2,-1.3) {f\/inal earn $= v_i\,v_k\,v_j$};
\end{tikzpicture}
$$

> **Intuition.** Splitting on the _first_ balloon leaves the two halves coupled,
> because a later burst can reach across the cut. Splitting on the _last_ balloon
> decouples them: once $k$ is the only survivor, its neighbors are pinned to the
> interval's walls, so whatever happened inside $(i,k)$ and $(k,j)$ could not have
> depended on the other side. "Last" turns a moving boundary into a fixed one.

**Minimum Cost to Cut a Stick** is the same idea in dual form. A stick has cut
positions inside it; making a cut costs the _current length_ of the piece being
cut. Fix which cut $k$ in $[i,j]$ is performed **last**: at that moment the piece
runs uncut from wall $i$ to wall $j$, so the cost equals the length
$x_j - x_i$, fixed; and the cuts in $(i,k)$ and $(k,j)$ were made earlier, each
within its own sub-piece, independently. Same recurrence, $O(n^3)$ over the cut
positions. The lesson generalizes: when the per-step cost depends on neighbors, ask
which step is _last_, since the last step is the one whose context is fully
determined by the interval endpoints.

::impl{algo="burst_balloons,min_cost_cut_stick"}

## Palindrome partitioning over a string

Interval DP also runs over strings. In **Palindrome Partitioning II** we cut a
string $s$ into pieces that are each palindromes, minimizing the number of cuts.
Precompute $\text{pal}[i,j]$, whether $s[i..j]$ is a palindrome, itself an
interval DP, since $s[i..j]$ is a palindrome iff $s_i = s_j$ and $s[i+1..j-1]$ is
(a length-$2$ shorter interval). Then let $\text{cut}[j]$ be the fewest cuts for
the prefix $s[0..j]$; for each $j$ we look back to the last palindromic piece:

$$
\text{cut}[j] = \min_{0 \le i \le j,\ \text{pal}[i,j]}
\begin{cases}
0 & i = 0,\\
\text{cut}[i-1] + 1 & i > 0.
\end{cases}
$$

The palindrome table is the interval DP (filled by increasing length); the cut
count is then a $O(n^2)$ sweep over it, a clean example of one interval DP feeding
a second, simpler one.

::impl{algo="palindrome_partitioning"}

## When $O(n^3)$ is too slow

The $O(n^3)$ cost comes from the inner scan over all splits $k$. For a class of
interval DPs (matrix-chain, optimal BST, and others whose cost obeys the
**quadrangle inequality**) the optimal split point is _monotone_ in the
endpoints, so the search for $k$ can be confined to a shrinking window. This is
**Knuth's optimization**, and it drops the running time to $O(n^2)$. We treat the
conditions and the proof in the lesson on [DP
optimizations](/algorithms/dynamic-programming/dp-optimizations); for now, note
only that the $O(n^3)$ here can sometimes be improved.[^skiena-dp]

## Where interval DP leads

Matrix-chain multiplication is the textbook instance of a deeper question: the
$O(n^3)$ DP here finds the cheapest _binary_ parenthesization, but the true
optimum over all associativity trees was shown by Hu and Shing (1982, 1984,
_SIAM J. Computing_) to be computable in $O(n \log n)$ by reducing matrix-chain to
a problem of triangulating a convex polygon — a drop from cubic that the DP
formulation does not suggest. The polygon-triangulation view generalizes:
**any** interval DP with a split point is a DP over triangulations, equivalently
over binary trees on the interval, which is why the number of states matches the
Catalan numbers.[^hushing]

Optimal binary search trees have a parallel history. Knuth's 1971 $O(n^2)$ algorithm
(via the monotone-root property, the [DP-optimizations
lesson](/algorithms/dynamic-programming/dp-optimizations)) is exact; Mehlhorn's
1975 result showed a simple _greedy_ near-optimal BST — always root at the key that
balances the weight — comes within a constant factor of optimal in $O(n)$ time,
the sort of "good enough, much faster" trade that recurs whenever the exact DP is a
bottleneck. The same static-optimality question, asked _online_, produced splay
trees (Sleator and Tarjan, 1985) and the still-open **dynamic optimality
conjecture**.

The "last operation" decoupling behind Burst Balloons is a reusable modeling
move: the same reframing underlies **CYK
parsing**. Parsing a context-free grammar asks for the best derivation of a
substring $[i, j]$, and the split point $k$ is the position where the top-level
rule $A \to BC$ divides the span — an interval DP whose "combine" multiplies
sub-derivation probabilities, giving $O(n^3 |G|)$ probabilistic parsing (the
foundation of pre-neural natural-language parsing) and, over the Boolean semiring,
CFG recognition (Cocke, Younger, Kasami, 1960s). RNA secondary-structure
prediction (Nussinov, 1978; Zuker, 1981) is the same interval DP again: fold a
strand $[i, j]$ by choosing which base pairs with position $i$, splitting the loop
into independent inner and outer intervals. Interval DP, the polygon triangulation,
CYK parsing, and RNA folding are the same recurrence in four settings.

## Takeaways

- **Interval DP** solves problems over a contiguous range: the state is a slice
  $[i,j]$, the recurrence picks a **split or pivot** $k$ that breaks the range
  into two independent parts, and the table is filled by **increasing interval
  length** so both parts are ready, typically $\Theta(n^2)$ states $\times$
  $O(n)$ splits $= O(n^3)$.
- **Matrix-chain multiplication** is the archetype:
  $m[i,j] = \min_{i \le k < j}\parens{m[i,k] + m[k+1,j] + p_{i-1}p_k p_j}$,
  $m[i,i]=0$, with a split table $s[i,j]$ to reconstruct the parenthesisation in
  $\Theta(n^3)$ time and $\Theta(n^2)$ space.
- **Optimal BSTs** reuse the same shape, replacing the combine term with the swept
  weight $w[i,j]$ of the interval.
- The **"last operation" trick** (Burst Balloons, Minimum Cost to Cut a Stick)
  fixes which move happens _last_ in $[i,j]$, not first, pinning the moving
  neighbor cost to the fixed interval walls and making the two sides truly
  **independent**.
- **Palindrome Partitioning II** runs interval DP over a string: a palindrome
  table by increasing length, then a linear cut-count sweep.
- **Knuth's optimization** cuts matrix-chain-style DPs to $O(n^2)$ when the
  **quadrangle inequality** makes the optimal split monotone — see the
  DP-optimizations lesson.

[^clrs-matrix]: **CLRS**, Ch. 15 — Dynamic Programming (§15.2): matrix-chain multiplication, the $m[i,j]$ recurrence, and reconstruction from the split table $s$ in $\Theta(n^3)$.
[^clrs-obst]: **CLRS**, Ch. 15 — Dynamic Programming (§15.5): optimal binary search trees as the same interval DP with the interval-weight combine term.
[^skiena-dp]: **Skiena**, § — Dynamic Programming: interval DPs as range subproblems combined at a split, and when monotonicity (Knuth) lowers the cubic cost.
[^hushing]: **Hu & Shing** (1982/1984, _SIAM J. Computing_): optimal matrix-chain parenthesization in $O(n\log n)$ via convex-polygon triangulation. **Mehlhorn** (1975): near-optimal BSTs greedily in $O(n)$. **Nussinov** (1978) and **Zuker** (1981): RNA secondary-structure folding as interval DP; the same recurrence underlies CYK CFG parsing.