Intro

I teach you two optimizations that skip unnecessary work. Both rely on a property called the quadrangle inequality. When it holds, the optimal split point is monotonic: $opt[i] \leq opt[i+1]$ for all $i$.

As $i$ increases, the best split never moves backward, so you can predict where to look. Knuth's improvement turns $O(n^3)$ interval DP (dynamic programming) into $O(n^2)$. D&C improvement turns $O(kn^2)$ partitioning DP into $O(kn \log n)$. By the end, you'll understand why these optimizations work, when to apply them, and how to implement them.