Dynamic Programming21 sections · 916 units
Open in Course

Section Recap

What we learned

You've learned two DP optimizations based on the quadrangle inequality:

1.1. D&C improvement: For layered DP. Solve middle first, recurse with bounded ranges. O(kn2)→O(kn^2) \to O(kn \log n)$$.

2.2. Knuth's improvement: For interval DP. Use opt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]. O(n3)→O(n^3) \to O(n^2)$$. The observation: monotonicity of optimal splits means you can skip most of the search space. Practice these on the problemset. They're advanced techniques, but once you understand them, they become mechanical to apply.