Knuth's Optimization

Prerequisite: Introduction to Dynamic Programming. Cousin: Divide and Conquer DP.

Knuth's optimization (Knuth–Yao speedup) is a range-DP trick that drops the usual O(n³) fill to O(n²) when the optimal split points are monotone.

This lesson follows CP-Algorithms — Knuth Optimization.

The recurrence

We care about transitions of the form

dp(i, j) = min_{i ≤ k < j}  [ dp(i, k) + dp(k+1, j) + C(i, j) ]

with a cost C(i, j) that does not depend on k. Naive range DP tries every k for every interval → O(n³) (assuming C is O(1)).

Let opt(i, j) be a maximizing argmin k (the rightmost best split). Knuth needs

opt(i, j−1) ≤ opt(i, j) ≤ opt(i+1, j)

When does it apply?

For a ≤ b ≤ c ≤ d, it is enough that C satisfies:

1. Monotone in the interval: C(b, c) ≤ C(a, d)
2. Quadrangle inequality (QI): C(a, c) + C(b, d) ≤ C(a, d) + C(b, c)

Then the opt sandwich above holds (proof sketch later). The classic case is

C(i, j) = sum of a subarray S[i..j]

(or any cost that inherits QI from such sums). Optimal BST is historically the motivating problem: the transition looks different, but the same opt inequality still holds.

Algorithm

Compute dp(i, j−1) and dp(i+1, j) (and their opts) before dp(i, j). Then only scan

k ∈ [opt(i, j−1), opt(i+1, j)]

instead of k ∈ [i, j−1].

Order that makes the neighbors ready: i from large to small, and for each i, j from i+1 upward.

int solve() {
    int N;
    // read N and input
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        // cost of interval [i, j]
        return 0;
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        // initialize dp[i][i]
    }

    for (int i = N - 2; i >= 0; i--) {
        for (int j = i + 1; j < N; j++) {
            int mn = INT_MAX;
            int cost = C(i, j);
            for (int k = opt[i][j - 1]; k <= min(j - 1, opt[i + 1][j]); k++) {
                if (mn >= dp[i][k] + dp[k + 1][j] + cost) {
                    opt[i][j] = k;
                    mn = dp[i][k] + dp[k + 1][j] + cost;
                }
            }
            dp[i][j] = mn;
        }
    }

    return dp[0][N - 1];
}

Use >= (or keep the rightmost k on ties) so opt is the maximum minimizing index, matching the inequality statement.

Complexity

Write Δ(i, j) = opt(i+1, j) − opt(i, j−1) (non-negative by monotonicity). The total number of k trials is about

Σ_{i,j} Δ(i, j)

Telescoping leaves only boundary terms of size O(n) per “diagonal band”, so the whole sum is O(n²) — not O(n³).

Tiny instance

Merge costs with a = [2, 3, 1, 4, 2] and C(i, j) = sum(a[i..j]), dp[i][i] = 0. Answer is 28.

🧪 Knuth vs naive k-loops (C++)

On practice

• Most uses are interval / matrix-chain / cutting DPs with the transition above.
• Hard part is proving QI (or proving the opt inequality directly).
• Subarray-sum costs are the easiest QI examples.
• If you can prove opt(i, j−1) ≤ opt(i, j) ≤ opt(i+1, j) even when C looks exotic (e.g. optimal BST), Knuth still applies.

Proof sketch

Assume QI + interval monotonicity on C. One shows that dp itself satisfies QI. Then, for fixed i and i ≤ p ≤ q < j,

dp_p(i, j−1) ≥ dp_q(i, j−1)  ⇒  dp_p(i, j) ≥ dp_q(i, j)

where dp_k(i, j) = C(i, j) + dp(i, k) + dp(k+1, j). Taking q = opt(i, j−1) forces every worse-or-equal left candidate to stay worse when the right endpoint grows, so opt(i, j) ≥ opt(i, j−1). The symmetric argument gives opt(i, j) ≤ opt(i+1, j).

Full write-up: CP-Algorithms.

Check: conditions & loops

Quiz

Knuth basics

1 / 4

Knuth targets which complexity drop for range DP?

Pick an answer to see if you are right.

Practice drills

Activity: Subarray cost

First line: n. Second: n ints a[0..n). Third: i j. Print sum(a[i..j]) (inclusive).

Contest problems

From CP-Algorithms:

Solve: UVA 10003 — Cutting Sticks (vjudge)

Tip

Cost of cutting [L,R] is R−L; Knuth applies.

Cheat sheet

Idea	Takeaway
Form	dp(i,j) = min_k dp(i,k)+dp(k+1,j)+C(i,j)
Need	opt(i,j−1) ≤ opt(i,j) ≤ opt(i+1,j)
Cost	Often QI + monotone C (e.g. subarray sums)
Loop	k only in that opt window
Order	i ↓, j ↑
Fast	O(n²) instead of O(n³)
Cousin	Divide-and-conquer DP (layered / different recurrence)