Lessons from Knuth's Optimization

$1.$ Knuth works for interval DP: $dp[i][j] = \min_{i \leq k \leq j}(dp[i][k-1] + dp[k+1][j]) + cost$.

$2.$ QI gives you the double bound on $opt[i][j]$.

$3.$ Process by length so bounds are available when needed.

$4.$ Store $opt[i][j]$ as you compute it. The pattern: combining subproblems (like BST, matrix chain, stone merge). This improvement avoids redundant computation. The time saved can be dramatic, turning an exponential solution into polynomial time.