Dynamic Programming • Optimization

Knuth Optimization

An advanced technique to optimize certain O(N³) Interval DP problems down to O(N²) by bounding the search space of the split point k.

Try Interactive Simulator

Overview

In standard Interval DP, we test `k` from `i` to `j`, taking O(N) time per state, leading to O(N³). Knuth Optimization limits `k` to a tiny range.

The Condition

Knuth applies when the cost function satisfies the Quadrangle Inequality and monotonicity on the lattice of intervals.

The Bounds

Instead of i ≤ k < j, we use opt[i][j-1] ≤ k ≤ opt[i+1][j]. The optimal split for [i, j] is bounded by the optimal splits of its slightly smaller sub-intervals.

Telescoping Sum

Because the upper bound of one interval is the lower bound of the next, the work done in the inner loop telescopes, amortizing the total time to exactly O(N²).

0

1

2

3

4

Search space is restricted. Instead of O(N) inner loop, it's O(1) amortized.

Code Tracker

:::

1// Instead of k from i to j-1

2// We bound k using previously found optimal splits

3for (let len = 2; len <= n; len++) {

4 for (let i = 0; i <= n - len; i++) {

5 let j = i + len - 1;

6 let kLeft = opt[i][j - 1];

7 let kRight = opt[i + 1][j];

8

9 for (let k = kLeft; k <= kRight; k++) {

10 // test cost and find minimum

11 // update opt[i][j] = best_k

12 }

13 }

14}