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

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.

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:

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.

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

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

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\cdot 2\cdot 7=158$. The completed table and its split choices:

from typing import NamedTuple, Sequence

class ChainSolution(NamedTuple):
  """
    The optimal cost of a matrix chain plus its parenthesisation string.\n
  """
  cost: int
  parenthesisation: str

def matrix_chain_cost(dimensions: Sequence[int]) -> int:
  """
    Fewest scalar multiplications to evaluate the chain whose dimension\n
    sequence is `dimensions` (length n+1 for n matrices). An empty chain\n
    (fewer than two dimensions) costs 0.\n
  """
  matrix_count: int = len(dimensions) - 1
  if matrix_count <= 1:
    return 0

  # min_cost[i][j] = best cost for the subchain A_i...A_j (1-indexed matrices).
  min_cost: list[list[int]] = [
    [0 for _ in range(matrix_count + 1)] for _ in range(matrix_count + 1)
  ]

  # fill by increasing chain length so shorter subchains are ready first.
  for length in range(2, matrix_count + 1):
    for start in range(1, matrix_count - length + 2):
      end: int = start + length - 1

      # try every split k, combining the two halves at cost p_{i-1} p_k p_j.
      best: int = -1
      for split in range(start, end):
        combine: int = (
          dimensions[start - 1] * dimensions[split] * dimensions[end]
        )
        candidate: int = min_cost[start][split] + min_cost[split + 1][end] + combine
        if best < 0 or candidate < best:
          best = candidate
      min_cost[start][end] = best

  return min_cost[1][matrix_count]

def matrix_chain_order(dimensions: Sequence[int]) -> ChainSolution:
  """
    Optimal cost and a fully parenthesised expression (matrices named\n
    A1, A2, ...) for the chain with the given `dimensions`.\n
  """
  matrix_count: int = len(dimensions) - 1
  if matrix_count <= 0:
    return ChainSolution(0, "")
  if matrix_count == 1:
    return ChainSolution(0, "A1")

  # min_cost holds the costs; split_at[i][j] records the winning split k.
  min_cost: list[list[int]] = [
    [0 for _ in range(matrix_count + 1)] for _ in range(matrix_count + 1)
  ]
  split_at: list[list[int]] = [
    [0 for _ in range(matrix_count + 1)] for _ in range(matrix_count + 1)
  ]

  # fill by increasing chain length, remembering each interval's best split.
  for length in range(2, matrix_count + 1):
    for start in range(1, matrix_count - length + 2):
      end: int = start + length - 1

      # try every split k and keep the cheapest along with its k.
      best: int = -1
      best_split: int = start
      for split in range(start, end):
        combine: int = (
          dimensions[start - 1] * dimensions[split] * dimensions[end]
        )
        candidate: int = min_cost[start][split] + min_cost[split + 1][end] + combine
        if best < 0 or candidate < best:
          best = candidate
          best_split = split

      min_cost[start][end] = best
      split_at[start][end] = best_split

  def build(start: int, end: int) -> str:
    """
      Reconstruct the parenthesised expression for A_start...A_end.\n
    """
    if start == end:
      return f"A{start}"

    # recurse on the two halves at the recorded split point.
    split: int = split_at[start][end]
    return f"({build(start, split)}{build(split + 1, end)})"

  return ChainSolution(min_cost[1][matrix_count], build(1, matrix_count))

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

from typing import Optional, Sequence

class BSTNode:
  """
    A node of a reconstructed optimal BST: the key index it holds plus its\n
    left and right children (None at the leaves).\n
  """

  def __init__(self, key_index: int) -> None:
    self.key_index: int = key_index
    self.left: Optional[BSTNode] = None
    self.right: Optional[BSTNode] = None

def optimal_bst_cost(weights: Sequence[float]) -> float:
  """
    Minimum expected search cost over a tree on keys with the given\n
    `weights` (probabilities or frequencies), ordered by key. An empty\n
    sequence costs 0.\n
  """
  key_count: int = len(weights)
  if key_count == 0:
    return 0.0

  # prefix[r] = sum of the first r weights, for O(1) interval weight queries.
  prefix: list[float] = [0.0 for _ in range(key_count + 1)]
  for index in range(key_count):
    prefix[index + 1] = prefix[index] + weights[index]

  def interval_weight(low: int, high: int) -> float:
    return prefix[high + 1] - prefix[low]

  # cost[i][j] = best expected cost for the keys [i, j]; empty range is 0.
  cost: list[list[float]] = [[0.0 for _ in range(key_count)] for _ in range(key_count + 1)]

  # fill by increasing interval length so subtrees are ready first.
  for length in range(1, key_count + 1):
    for low in range(0, key_count - length + 1):
      high: int = low + length - 1
      weight: float = interval_weight(low, high)

      # try each key as root; rooting charges the interval weight once more.
      best: float = -1.0
      for root in range(low, high + 1):
        left: float = cost[low][root - 1] if root > low else 0.0
        right: float = cost[root + 1][high] if root < high else 0.0
        candidate: float = left + right + weight
        if best < 0 or candidate < best:
          best = candidate
      cost[low][high] = best

  return cost[0][key_count - 1]

def optimal_bst(weights: Sequence[float]) -> tuple[float, Optional[BSTNode]]:
  """
    Minimum expected cost and the root of an optimal BST (a tree of BSTNode\n
    objects keyed by index) for the given `weights`. Returns (0, None) for\n
    an empty sequence.\n
  """
  key_count: int = len(weights)
  if key_count == 0:
    return 0.0, None

  # prefix[r] = sum of the first r weights, for O(1) interval weight queries.
  prefix: list[float] = [0.0 for _ in range(key_count + 1)]
  for index in range(key_count):
    prefix[index + 1] = prefix[index] + weights[index]

  def interval_weight(low: int, high: int) -> float:
    return prefix[high + 1] - prefix[low]

  # cost holds the expected costs; root_of[i][j] records the chosen root.
  cost: list[list[float]] = [[0.0 for _ in range(key_count)] for _ in range(key_count + 1)]
  root_of: list[list[int]] = [[0 for _ in range(key_count)] for _ in range(key_count)]

  # fill by increasing interval length, remembering each interval's best root.
  for length in range(1, key_count + 1):
    for low in range(0, key_count - length + 1):
      high: int = low + length - 1
      weight: float = interval_weight(low, high)

      # try each key as root and keep the cheapest along with its index.
      best: float = -1.0
      best_root: int = low
      for root in range(low, high + 1):
        left: float = cost[low][root - 1] if root > low else 0.0
        right: float = cost[root + 1][high] if root < high else 0.0
        candidate: float = left + right + weight
        if best < 0 or candidate < best:
          best = candidate
          best_root = root

      cost[low][high] = best
      root_of[low][high] = best_root

  def build(low: int, high: int) -> Optional[BSTNode]:
    """
      Reconstruct the optimal subtree on keys [low, high].\n
    """
    if low > high:
      return None

    # hang the recorded subtrees beneath the chosen root.
    root: int = root_of[low][high]
    node: BSTNode = BSTNode(root)
    node.left = build(low, root - 1)
    node.right = build(root + 1, high)
    return node

  return cost[0][key_count - 1], build(0, key_count - 1)

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:

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.

from typing import Sequence

def burst_balloons(values: Sequence[int]) -> int:
  """
    Maximum coins earned by bursting every balloon in `values`. An empty\n
    sequence earns 0.\n
  """
  if not values:
    return 0

  # Pad with sentinel 1s so the walls just outside the range are never burst.
  padded: list[int] = [1, *values, 1]
  wall_count: int = len(padded)

  # best[left][right] = max coins from bursting all balloons strictly inside
  # the open interval (left, right), with left and right standing as walls.
  best: list[list[int]] = [[0 for _ in range(wall_count)] for _ in range(wall_count)]

  # fill by increasing interval span so inner intervals are solved first.
  for length in range(2, wall_count):
    for left in range(0, wall_count - length):
      right: int = left + length

      # fix the balloon burst last; its neighbors are pinned to the walls.
      most: int = 0
      for last in range(left + 1, right):
        coins: int = padded[left] * padded[last] * padded[right]
        candidate: int = best[left][last] + best[last][right] + coins
        most = max(most, candidate)
      best[left][right] = most

  return best[0][wall_count - 1]

from typing import Sequence

def min_cost_cut_stick(stick_length: int, cuts: Sequence[int]) -> int:
  """
    Minimum total cost to make every cut in `cuts` on a stick of length\n
    `stick_length`. With no cuts the cost is 0.\n
  """
  if not cuts:
    return 0

  # Walls = the two ends plus every cut position, sorted; the endpoints of a
  # sub-piece are always wall positions, so a "last" cut runs wall to wall.
  positions: list[int] = sorted({0, stick_length, *cuts})
  wall_count: int = len(positions)

  # best[low][high] = min cost to make all cuts strictly between walls
  # low and high (exclusive).
  best: list[list[int]] = [[0 for _ in range(wall_count)] for _ in range(wall_count)]

  # fill by increasing sub-piece span so inner pieces are solved first.
  for length in range(2, wall_count):
    for low in range(0, wall_count - length):
      high: int = low + length
      piece_length: int = positions[high] - positions[low]

      # fix the last cut; its piece spans wall to wall at a flat cost.
      cheapest: int = -1
      for last in range(low + 1, high):
        candidate: int = best[low][last] + best[last][high] + piece_length
        if cheapest < 0 or candidate < cheapest:
          cheapest = candidate
      best[low][high] = max(cheapest, 0)

  return best[0][wall_count - 1]

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.

def palindrome_table(text: str) -> list[list[bool]]:
  """
    is_palindrome[i][j] for every substring text[i..j], filled by\n
    increasing interval length.\n
  """
  length: int = len(text)

  # every single character is a palindrome on its own.
  is_palindrome: list[list[bool]] = [
    [False for _ in range(length)] for _ in range(length)
  ]
  for start in range(length):
    is_palindrome[start][start] = True

  # grow by span: text[i..j] holds iff its ends match and the inside does.
  for span in range(2, length + 1):
    for start in range(0, length - span + 1):
      end: int = start + span - 1
      ends_match: bool = text[start] == text[end]
      inner_ok: bool = span == 2 or is_palindrome[start + 1][end - 1]
      is_palindrome[start][end] = ends_match and inner_ok

  return is_palindrome

def min_palindrome_cuts(text: str) -> int:
  """
    Fewest cuts so every piece of `text` is a palindrome. The empty string\n
    and any palindrome need 0 cuts.\n
  """
  length: int = len(text)
  if length <= 1:
    return 0

  is_palindrome: list[list[bool]] = palindrome_table(text)

  # cut_count[end] = fewest cuts for the prefix text[0..end].
  cut_count: list[int] = [0 for _ in range(length)]
  for end in range(length):

    # a palindromic prefix needs no cuts at all.
    if is_palindrome[0][end]:
      cut_count[end] = 0
      continue

    # else cut before the last palindromic piece, minimizing over its start.
    best: int = end  # worst case: cut before every character.
    for start in range(1, end + 1):
      if is_palindrome[start][end]:
        candidate: int = cut_count[start - 1] + 1
        if candidate < best:
          best = candidate
    cut_count[end] = best

  return cut_count[length - 1]

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 can sometimes be improved.³

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

Optimal binary search trees have a parallel history. Knuth's 1971 $O(n^2)$ algorithm (via the monotone-root property, the DP-optimizations lesson) 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}\left(m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j\right)$, $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.