CONCEPT · Expert
Dynamic programming
also DP · memoization
Solve overlapping subproblems with a named state and a transition. Rank 4 is knapsack/LIS/grids; Rank 9 adds masks, intervals, and digits.
Intuition
If the answer for a bigger instance is a short combination of answers for strictly smaller instances, store them.
When to reach for it
- Knapsack, LIS, path counts on DAGs
- Digit DP, interval DP, DP on trees and broken profiles
Usual pits
- State missing a dimension you actually need
- Transition that is O(n) too expensive in the inner loop
- Not initializing base cases