Dynamic programming
Overlapping subproblems with optimal substructure: counting ways, minimizing cost, knapsack, and edit distance.
High interview relevanceRoadmap: Advanced
| Time | Number of states × transitions per state |
|---|---|
| Space | Depends on memoization or tabulation |
Why it costs this much
Each state is computed once and cached, so the total work is the number of states times the work to combine one state.
Code
from functools import lru_cache
@lru_cache(maxsize=None)
def climb(n): # states: n; transitions per state: 2
if n <= 1:
return 1
return climb(n - 1) + climb(n - 2) # O(n) total: each state computed onceCommon pitfalls
Define the state before writing code. Memoization also uses stack depth, and tabulation can often keep only the previous row. Knapsack is pseudo-polynomial because it depends on the capacity value.