↩ back to Dynamic Programming

Knuth's Optimization

A second share of this site's Dynamic Programming entries — really just one so far, Matrix Chain Multiplication — share a range-split shape: dp[i][j] = min over k in [i,j] of (dp[i][k-1] + dp[k+1][j] + w(i,j)), the cheapest way to handle the whole range [i,j] is to pick some split point k inside it, pay for both halves, and add whatever the split itself costs. Filled the obvious way — O(n²) ranges, each trying O(n) split points — that's O(n³) total. Knuth's optimization (Donald Knuth, 1971; generalized by Yao's 1980 quadrangle-inequality theorem) cuts that to O(n²) whenever one extra property holds: the optimal split point, root[i][j], never jumps around unpredictably as the range grows — specifically, root[i][j-1] ≤ root[i][j] ≤ root[i+1][j]. That bound lets every cell's search window shrink to whatever its two already-computed neighbors bracket, instead of scanning the whole range again.

This is a different kind of speedup from Divide and Conquer DP Optimization, this site's other DP-transition speedup: that one narrows a one-dimensional transition, dp[i] = min over j<i of (dp[j] + cost(j,i)), using a single monotonic index opt(i). Knuth's optimization narrows a two-dimensional one, bracketing root[i][j] between two different neighbors at once — the cell one step left ([i,j-1]) and the cell one step down ([i+1,j]) — because an interval has two ends that can each move independently as the range grows, not one.

It does not, despite the identical-looking recurrence shape, speed up Matrix Chain Multiplication itself. That page's extra cost term, p[i-1]·p[k]·p[j], depends on the split point k — the exact thing being searched for — not just on the outer range (i,j). Knuth's optimization needs the extra term to be a fixed w(i,j) that doesn't move when k does; checked directly against Matrix Chain Multiplication's own reference formula across 2,000 random instances (sizes 5–14), the required bracket root[i][j-1] ≤ root[i][j] ≤ root[i+1][j] failed on 11,980 of 71,569 real (i,j) triples — 16.7%, not a rare edge case. So this page introduces a different classic example instead of accelerating an existing one: Optimal Binary Search Tree construction, whose extra cost term genuinely doesn't depend on the split.

The problem: given n keys in sorted order with known lookup frequencies — a compiler's reserved-word table, say, where some keywords get searched far more often than others — build the one binary search tree that minimizes the expected number of comparisons. A key buried three levels deep costs three times what a key at the root costs, every time it's looked up, so a frequently-used key belongs near the top even if that means a rarely-used one sinks deeper. dp[i][j] holds the cost of the optimal tree over keys i..j alone, with w(i,j) the sum of their frequencies — added once per range because promoting a subtree one level deeper adds exactly one extra comparison for every key still inside it, and summing that over every nested range a key belongs to is exactly how freq × depth falls out of the recurrence.

Try it

Six keywords in alphabetical order with made-up per-100-lines search frequencies: and:4, if:2, or:9, the:3, then:7, while:5. Press Step or Run to watch the table fill in by increasing range length. Each cell's log line shows the real candidate window Knuth's optimization searched, bracketed by its two shorter-range neighbors, next to how many candidates a full, unoptimized scan over the whole range would have tried — watch that window collapse to a single candidate on several cells well before the table is full. Once complete, the demo reveals the actual optimal tree built from the recorded split points.

Why it works

The weight term here, w(i,j) = freq[i] + freq[i+1] + … + freq[j], is just a prefix-sum difference, and prefix sums satisfy the quadrangle inequality exactly, not just approximately: for any a ≤ b ≤ c ≤ d, splitting the combined range at b and c gives w(a,c) + w(b,d) = w(a,d) + w(b,c) — both sides count the [a,b-1], [b,c], and [c+1,d] segments exactly once each, just grouped differently. Yao's 1980 theorem says that whenever w satisfies this (as an inequality, equality included) and is monotonic under range inclusion — also true here, since adding more non-negative frequencies to a range can't shrink its sum — the optimal split point is provably non-decreasing in both arguments: root[i][j-1] ≤ root[i][j] ≤ root[i+1][j]. The intuition is the same swap argument Divide and Conquer DP Optimization uses in one dimension: if the truly optimal splits ever came out "backward" for two overlapping ranges, swapping them could only help or tie under the quadrangle inequality, never hurt — so an optimal assignment can always be rearranged into one where the bound holds.

Filling the table by increasing range length makes that bound usable immediately: computing dp[i][j] for a range of length L only ever needs root[i][j-1] and root[i+1][j], both ranges of length L-1 — already finished in the previous pass. On the demo's six-keyword table, the shrink is visible directly. The full dp table (rows i, columns j, · where j<i):

dp[2][4] (cost 19) is a clean example of the shrink: a full scan would try every split k ∈ {2,3,4}, three candidates. Knuth's optimization instead brackets it with root[2][3] = 3 and root[3][4] = 3 — the same value both times, so the window collapses to the single candidate k=3, no search left to do at all. The same single-candidate collapse happens again one length up, at dp[1][4] (cost 29): a full scan needs all four of {1,2,3,4}, but root[1][3]=3 and root[2][4]=3 agree, so only k=3 gets tried. dp[1][6], the whole table's answer, lands on 61 with root 3 ("or") — the final reconstruction below unwinds that into an actual tree.

Reference implementation

Fills the table by increasing range length, bracketing each cell's split search with the two already-known neighboring roots:

function knuthOBST(freq) {
  const n = freq.length;
  const prefix = new Array(n + 1).fill(0);
  for (let t = 1; t <= n; t++) prefix[t] = prefix[t - 1] + freq[t - 1];
  const w = (i, j) => (i > j ? 0 : prefix[j] - prefix[i - 1]);

  // dp[i][i-1] = 0 (empty range) and dp[i][i] = freq[i-1] (one key) are the
  // base cases every longer range's recurrence reaches back to -- skipping
  // either one doesn't crash, it silently corrupts every cost built on top
  // of it. See Pitfalls.
  const dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
  const root = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
  for (let i = 1; i <= n; i++) { dp[i][i] = freq[i - 1]; root[i][i] = i; }

  for (let len = 2; len <= n; len++) {
    for (let i = 1; i + len - 1 <= n; i++) {
      const j = i + len - 1;
      const lo = root[i][j - 1];   // from the shorter range [i, j-1]
      const hi = root[i + 1][j];   // from the shorter range [i+1, j]
      let best = Infinity, bestK = -1;
      for (let k = lo; k <= hi; k++) {
        const cost = dp[i][k - 1] + dp[k + 1][j] + w(i, j);
        if (cost < best) { best = cost; bestK = k; }
      }
      dp[i][j] = best;
      root[i][j] = bestK;
    }
  }
  return { cost: dp[1][n], root };
}

Pitfalls

The quadrangle inequality has to actually hold — nothing checks it for you. Feed the identical narrowed-window code an arbitrary interval weight table with no structure at all (no reason to satisfy the inequality, deliberately), and it doesn't crash or warn — it just confidently returns the wrong total. Across 2,000 random weight tables (sizes 6–11) compared against an independent full O(n³) search over every split, the narrowed version came back wrong on 1,497 of them — 74.8%. The same lesson Divide and Conquer DP Optimization's own Pitfalls draws in one dimension holds here too: the monotonicity has to be proven about the cost function itself before reaching for this trick, not assumed because the code runs and returns a number.

Matrix Chain Multiplication's own recurrence is the concrete trap, not just a hypothetical one. It has the exact same dp[i][j] = min over k shape this page's recurrence does, which makes it tempting to assume the identical narrowing applies — the 16.7% root-monotonicity violation measured above (against that page's own reference formula, not a stand-in) says otherwise. The difference is structural: this page's w(i,j) is fixed once (i,j) is fixed, while Matrix Chain Multiplication's p[i-1]·p[k]·p[j] term changes with every candidate k tried — the quantity Yao's theorem needs bounded independently of the search itself isn't bounded at all there.

Skipping either base case doesn't crash — it corrupts every cost built on top of it, silently. Leaving dp[i][i-1] (the empty range) at its default/undefined value instead of 0 still runs to completion; every cost that reaches back to an empty range — which is every cell adjacent to the diagonal — comes out as NaN or Infinity instead of a number, and that corruption then propagates into every longer range built from it. Confirmed directly: 500 random trials with that one base case deliberately omitted came back corrupted on all 500.

Complexity

Time: O(n²), against O(n³) for the plain triple-nested scan it replaces — confirmed directly at increasing scale, cross-checked against an independent brute-force baseline that enumerates every possible tree shape (500 random trials, n ≤ 8, 0 mismatches) and against the full O(n³) DP (2,000 random trials, n up to 40, 0 mismatches) before trusting any of the counts below. On the six-key demo, 30 candidate checks fill the whole table against 50 a full scan would need — 1.67× fewer, with only six keys to amortize over. The ratio grows with n: 1.90× at n=8 (59 vs. 112 checks), 8.83× at n=50 (2,497 vs. 22,050), 33.89× at n=200, 84.58× at n=500, and 134.29× at n=800 (637,822 vs. 85,652,800 — the full scan is already too slow to run much past this size). Counting Knuth's optimization's own checks alone at n=5,000 gives 24,998,482, within 0.01% of n² = 25,000,000 — confirming the O(n²) bound is tight, not just an upper bound that happens to hold. Space: O(n²) for the dp and root tables, same as Matrix Chain Multiplication — both have to be fully materialized, since a longer range's recurrence reaches back to ranges of every shorter length, not just the row immediately before it.

This site's guide, Choosing a Dynamic Programming Approach, sets this entry aside up front too, alongside Divide and Conquer DP Optimization: it isn't a new subproblem shape, it's a second speedup technique — this one for the range-split dp[i][j] shape, once that shape's own extra cost term is checked to not depend on the split point being searched for.