Knuth's Optimization - Walkthrough

Interval DP: $dp[i][j] = \min_{k} (dp[i][k] + dp[k+1][j]) + cost[i][j]$. With QI, $opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]$.

For interval $[0, 4]$: $opt[0][3] \leq opt[0][4] \leq opt[1][4]$. The search range for $opt[0][4]$ is bounded. Fill by diagonal (increasing interval length). For each interval, the bounded search guarantees amortized $O(1)$ per interval. Total: $O(n^2)$ for all intervals, down from $O(n^3)$. Critical for $n = 5000$ problems.