When to use
Use dynamic programming when a problem has overlapping subproblems (same computation repeated) and optimal substructure (optimal solution built from optimal sub-solutions).
Signs
"find minimum cost," "count the number of ways," "longest/shortest subsequence," "can you reach."
Rules
- Define state (what changes between subproblems) and recurrence (how states relate)
- Top-down with @cache is easiest to write; bottom-up tabulation avoids recursion limits and is often faster
- ALWAYS check if you can reduce space by keeping only the previous row/state instead of the full table
- NEVER memoize without verifying overlapping subproblems exist
Approach
- Identify the state variables
- Write the recurrence relation
- Choose top-down (@cache) or bottom-up (tabulation)
- Optimize space if possible
Example
"Min coins for amount" → state = remaining amount. Recurrence: dp(n) = 1 + min(dp(n - c) for c in coins). Use @cache for top-down; reduce to O(amount) space.