Category
Level
Knuth Optimization speeds up a class of interval dynamic programming (DP) from O(n^3) to O(n^2) by exploiting the monotonicity of optimal split points.