Knuth's DP Optimization — the Monotone Optimal Split

Interval DP dp[i][j] = C(i,j) + minₙ(dp[i][k] + dp[k+1][j]). Watch the table fill by increasing length, and the inner k-scan shrink to the window [opt[i][j-1], opt[i+1][j]] instead of the full range. Total work telescopes from O(n³) to O(n²).

step 0

DP table (filled by increasing interval length)

computed active (i,j) diagonal / not yet

Inner k-scan for the active interval

interval —
outside window (skipped by Knuth) inside window scanning now chosen opt
Press Step to begin. The DP is filled diagonal by diagonal (increasing interval length). For each interval the inner loop scans only k in [opt[i][j-1], opt[i+1][j]].
Self-contained visualization. Cost C(i,j) is a non-negative range sum (frequencies / stone sizes), which satisfies the quadrangle inequality and monotonicity — so opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j] and the restricted scan is correct. See junior.md and professional.md for the proof that the per-length window widths telescope to O(n).