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: for all .
As increases, the best split never moves backward, so you can predict where to look. Knuth's improvement turns interval DP (dynamic programming) into . D&C improvement turns partitioning DP into . By the end, you'll understand why these optimizations work, when to apply them, and how to implement them.