Skip to content

Knuth Optimization Ladder

This ladder is for the narrow interval-DP lane where the baseline O(n^3) split-point recurrence can be reduced to O(n^2) by a monotone opt window.

Who This Is For

Use this ladder if:

  • you already recognize plain Interval DP
  • you can write the merge-style recurrence
  • you now need the exact stronger optimization, not a broader theory tour

Core

  • split-point interval recurrence
  • cost(l, r) independent of k
  • opt[l][r-1] <= opt[l][r] <= opt[l+1][r]

Target skill:

  • know when Knuth is the exact optimization family, not divide-and-conquer DP

Exact Starter

Target skill:

  • turn a proven O(n^3) merge-style interval DP into the standard O(n^2) table fill

Flagship Rep

Target skill:

  • combine prefix-sum interval cost with the exact opt search window

Stretch

Target skill:

  • separate interval-state speedup from partition-row speedup

Exit Criteria

You are ready to move on when:

  • you can state the recurrence shape from memory
  • you know why cost(l, r) must not depend on k
  • you can write the opt[l][r-1] .. opt[l+1][r] window without re-deriving loop order each time

External Practice