Groups
Category
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.
Interval DP solves problems where the optimal answer for a segment [i, j] depends on answers of its subsegments.