All patterns
Dynamic Programming
Solve each distinct subproblem once and reuse it.
time O(states × transition)space O(states)
What it is
When a recursion revisits the same states, cache the answers. Cost is (number of states) × (work per state). Top-down memoization is easiest to write; bottom-up tabulation allows space optimization.
When to reach for it
- Overlapping subproblems
- Optimal substructure
- Count ways, min cost, max value, feasibility
Clues in the problem
- Naive recursion is exponential
- State can be described by one to three integers
Template
from functools import lru_cachedef solve(n):@lru_cache(None)def go(i):if i <= 1:return ireturn go(i - 1) + go(i - 2)return go(n)
Practice problems
- Climbing Stairs
- House Robber
- Coin Change
- Longest Common Subsequence
- 0/1 Knapsack
Common mistakes
- State that misses a dimension the answer depends on
- Recursion depth limits in Python or Java
- Keeping the whole table when only the last row is needed