D&C and Knuth Overview

D&C improvement: For layered DP like $dp[g][i] = \min_{j < i}(dp[g-1][j] + cost(j,i))$. Uses divide and conquer to exploit monotonicity. $O(n^2) \to O(n \log n)$ per layer. Knuth's improvement: For interval DP like $dp[i][j] = \min_k(dp[i][k] + dp[k+1][j]) + cost$.

Uses a double bound on $k$. $O(n^3) \to O(n^2)$ total. Both require QI. The difference is the DP structure: layers vs intervals.