DP is recursion with the recomputation removed. The hard part is never the code — it is choosing the state.
The four questions
- What is the state? (what do I need to remember)
- What is the transition? (how do states combine)
- What is the base case?
- What is the order? (every state must be ready before it is used)
Foundations
- Introduction to DP
- Memoization (top-down)
- Tabulation (bottom-up)
- Designing States
- Space Optimization
Classic Problems
- Knapsack — 0/1, unbounded, bounded, fractional
- Longest Increasing Subsequence
- Longest Common Subsequence
- Edit Distance
- Matrix Chain Multiplication
- Coin Change and Counting
- Partition Problems
DP Flavours
- Interval DP
- Tree DP
- Rerooting DP
- Bitmask DP
- Digit DP
- Probability and Expected Value DP
- DP on DAGs
- Broken Profile DP
- Game DP
Optimizations
- Divide and Conquer DP
- Convex Hull Trick
- Monotone Queue Optimization
- Knuth Optimization
- Aliens Trick (Lagrangian)
- Slope Trick
- SMAWK and Monotone Matrices
- Matrix Exponentiation on DP
- SOS DP
See also: Subset DP · DP Cheatsheet