What Is Knuth's Optimization?

Interval DP has form: $dp[i][j] = \min_{i \leq k \leq j}(dp[i][k-1] + dp[k+1][j]) + cost(i,j)$. Some variants use $k < j$ depending on the problem.

Naive: $O(n^2)$ states, $O(n)$ choices per state = $O(n^3)$. Knuth's observation: if cost satisfies QI, then $opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]$. This double bound limits where to search for $k$. Summed over all states, total work becomes $O(n^2)$.