Interval DP

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, and once you see its shape you will find it everywhere: parenthesising a product, building an optimal search tree, bursting balloons, cutting a stick, 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.¹

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. 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: if a cheaper parenthesisation of a side existed, substituting it would lower the total. Overlapping subproblems: both sides are again contiguous subchains, and the same subchain is reached by many different outer choices.

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:

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$.

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.

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.

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.

The interval-DP recipe

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

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 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:

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:

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.²

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 exactly the adjacency that sets the cost. The fix is to 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 are exactly 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$ stood as fixed walls, and likewise $(k,j)$ played out against walls $k$ and $j$. The two sides never touch. They are independent:

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 is exactly 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.

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+\mathrm{1..}j-1]$ is (a length-$2$ shorter interval). Then let $\text{cut}[j]$ be the fewest cuts for the prefix $s[\mathrm{0..}j]$; for each $j$ we look back to the last palindromic piece:

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.

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; for now, note only that the $O(n^3)$ here is not always the last word.³

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}(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.