Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure by computing each subproblem once and reusing the result. The two styles are memoization (top-down) and tabulation (bottom-up).
Naive recursion recomputes the same subproblems exponentially. DP caches them, collapsing exponential work into polynomial.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Direction | top-down recursion | bottom-up iteration |
| Computes | only needed states | all states |
| Risk | stack overflow | none |
| Space | can be trimmed | often reducible to O(1) rows |
Fibonacci: from O(2ⁿ) naive to O(n) time, O(n) (or O(1)) space.
Use DP when subproblems overlap. Define the state and recurrence carefully — that is the hard part. If subproblems don't overlap, plain divide-and-conquer is enough.
DP converts intractable exponential problems — shortest paths, edit distance, knapsack — into efficient ones.
The skill of identifying state and recurrence is among the most valued in algorithm interviews.
It underlies real systems from diff tools to bioinformatics sequence alignment.