Interval DP: Choosing the Last Operation Instead of the First

A class of problems asks for the best way to decompose a sequence into nested pieces: parenthesize a chain of matrix multiplications, build a binary search tree over sorted keys with given access frequencies, merge a row of stones where each merge costs the combined weight, or burst balloons where each burst earns the product of its current neighbours. In each case the object being built is a binary tree over a contiguous range, and the number of such trees is the Catalan number C(n) = (2n)! / ((n+1)! n!), which is asymptotic to 4^n / (n^{3/2} \sqrt{\pi}). Enumerating them is hopeless past n = 20.

The interval DP works because the tree can be indexed by its root. Fixing the root splits the range into a left part and a right part, and those two parts are independent. The state becomes the range, the transition enumerates the root, and the table is O(n²) cells with O(n) transitions each.

The reversal that makes it work

The natural way to describe these problems is forward: choose the first split, then the first split of each half, and so on. That description is a tree-recursive enumeration, and the subproblems it generates depend on which splits were already made. The interval DP instead asks: which split was made last?

The last operation on a range [lo, hi] is a single split at some k, after which the two sides were already fully processed. Because it is last, the two sides are independent and their costs are additive. This gives the canonical recurrence:

dp[lo][hi] = min over lo <= k < hi of ( dp[lo][k] + dp[k+1][hi] + cost(lo, k, hi) )

The subproblems are indexed only by their boundaries, so there are n(n+1)/2 of them, and each is solved once. Total work is Θ(n³) and space Θ(n²). The cost term is the only problem-specific part; everything else is the same table.

This is the sufficiency principle from state sufficiency applied to a sequence: after the last split, no decision inside the left half can affect the right half, so the boundary indices are a complete summary of the past. Note what is not in the state — which splits came before, how many merges happened, what the intermediate values were. All of that is captured by the subproblem’s own optimal value.

Ordering the table

The dependency is from shorter ranges to longer ones, because dp[lo][k] and dp[k+1][hi] are both strictly shorter than [lo, hi]. Iterating by length is therefore a valid topological order, and it is the standard loop nest:

def merge_cost(weights):
    n = len(weights)
    prefix = [0] * (n + 1)
    for i, w in enumerate(weights):
        prefix[i + 1] = prefix[i] + w
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):          # ranges of this length are ready to fill
        for lo in range(0, n - length + 1):
            hi = lo + length - 1
            total = prefix[hi + 1] - prefix[lo]
            dp[lo][hi] = min(dp[lo][k] + dp[k + 1][hi] for k in range(lo, hi)) + total
    return dp[0][n - 1] if n else 0

Two details carry weight. The prefix sum makes cost(lo, hi) — the total weight of the range — an O(1) lookup rather than an O(n) loop, which is the difference between Θ(n³) and Θ(n⁴). And the + total sits outside the min because the merge cost is the same regardless of where the split falls; in matrix-chain multiplication the analogous term does depend on k and must go inside.

The alternative to length iteration is memoized recursion on (lo, hi), which visits the same cells in an order determined by the recursion. It is equally correct and uses O(n) stack depth, so a range of 10^5 characters overflows a default Python stack. The bottom-up form has no such limit.

Where the “last operation” reading comes from

The trick is not always obvious in the problem statement, and three examples show the range of disguises.

Matrix-chain multiplication. Multiply n matrices with dimensions p_0 × p_1 × … × p_n. The parenthesization determines the order, and a parenthesization is a binary tree over the matrices. The last multiplication combines the result of [lo..k] with the result of [k+1..hi], at cost p_lo · p_{k+1} · p_{hi+1}. The recurrence is exactly the canonical one with a k-dependent cost.

Bursting balloons. Given a row of balloons with numbers, bursting balloon i earns the product of its current left and right neighbours, and neighbours become adjacent afterwards. Working forward is hard because bursting changes the neighbourhood. Working backward is easy: the last balloon burst in a range has, as its neighbours, the fixed boundaries lo − 1 and hi + 1. So dp[lo][hi] = max over k of dp[lo][k-1] + dp[k+1][hi] + a[lo-1]·a[k]·a[hi+1], with sentinel balloons of value 1 at both ends.

Optimal binary search tree. Keys are sorted with search probabilities. A tree over [lo..hi] has a root k; the left subtree holds [lo..k-1] and the right [k+1..hi]. Every key in the range descends one level when the root is placed above it, so the cost of the whole range includes the sum of probabilities in the range, and the recurrence adds that sum at every level.

In each case the state is the same pair of indices, and the only difference is what the split costs. That uniformity is why the technique transfers: recognizing that a problem’s solution is a binary tree over a contiguous range is the whole insight, and the recurrence follows mechanically.

Ties, reconstruction, and the shape of the answer

The table stores the optimum but not the tree. Reconstruction needs the split index that achieved it, either in a parallel O(n²) array or by recomputation during the traceback. Recomputing is cheap here — O(n) per level, O(n²) total — and avoids the second array, which for n = 10^4 would be another 100 million entries.

Ties matter in a specific way. When several splits achieve the same optimum, the reconstructed tree depends on which one the traceback picks. A consistent rule (the smallest k, say) makes the output deterministic, which matters if the tree is compared or cached. Inconsistent tie-breaking between the forward pass and the traceback produces a tree whose cost does not match the reported optimum: the traceback follows a split that was not the one recorded as optimal for that cell, and the remaining splits are then taken from the wrong subproblem.

Empty ranges need a convention. dp[lo][lo] is a single element with no split, and its value is zero for matrix chain and merge problems but not for the optimal-BST case, where a single key still costs its own probability. Base cases are where interval DPs most often go wrong, because a range of length one has a non-trivial value in some formulations and a trivial one in others.

The quadrangle inequality removes a factor

The O(n³) bound comes from enumerating all n split points per cell. For some cost functions, the optimal split index is monotone in the range: if opt[lo][hi] is the argmin, then

opt[lo][hi-1] <= opt[lo][hi] <= opt[lo+1][hi]

When this holds, the search for k can start at opt[lo][hi-1] and stop at opt[lo+1][hi] instead of running over the whole range. The number of k values examined is then bounded, for each length, by the telescoping sum Σ (opt[lo+1][hi] − opt[lo][hi-1] + 1) over the lo of that length, which is O(n). All cells of a fixed length therefore cost O(n), and the whole table costs Θ(n²).

The monotonicity is a consequence of the cost function satisfying the quadrangle inequality, which is the Monge condition on the cost matrix:

w(a, c) + w(b, d) <= w(a, d) + w(b, c)     for a <= b <= c <= d

Knuth proved this for optimal binary search trees using the weights of the keys, which is why the optimization carries his name; the resulting algorithm computes the optimal BST in Θ(n²) time and space. The condition is a property of the cost, not of the algorithm, and it must be proved per problem. Applying the bound without the proof yields a fast program with no correctness guarantee — and the failure is not a crash but a wrong answer on inputs where the monotonicity fails, which may be a single input in a family that no random test happens to reach.

For merge-cost problems the split cost is the total weight of the range, and with non-negative weights that cost is additive over the elements and monotone in the range, which is what makes the argmin monotone; this is the instance Knuth’s argument covers. For other cost functions the check has to be made against the specific expression: the inequality is a condition on the cost, and non-negative weights alone do not establish it for an arbitrary split cost. Where it fails, the O(n³) bound stands.

Relation to other table shapes

Interval DP is the two-index member of a family. The sequence-alignment table in edit distance is also indexed by two positions, but its transitions step by one character rather than jumping to an arbitrary split, so its work is Θ(n²) rather than Θ(n³). The difference is the transition’s reach: a single-step move has one source per cell, while a split move has n.

The same jump structure appears in the divide-and-conquer optimization covered in monotone decision points, where the recurrence is one-dimensional but the transition scans a range, and monotonicity of the argmin again collapses the scan. Both techniques exploit the same phenomenon — that optimal choices vary smoothly with the state — and both require a proof of that smoothness.

On trees, the analogous decomposition is by subtree rather than by interval, and the resulting recurrence is a knapsack over children. That shape, including the O(n²) merge cost that appears when subtrees are combined, is treated in tree DP and rerooting.