Overview
Dynamic programming, per NIST's own definition, solves an optimization problem by caching subproblem solutions (memoization) instead of recomputing them, and it only actually helps when a problem has overlapping subproblems, the same smaller subproblem genuinely recurring across different branches of the larger recursive structure. Naive recursive Fibonacci is the canonical example: fib(n-2) gets computed once directly and again inside the fib(n-1) branch, and that duplication compounds into roughly 2^n total calls; caching each result the first time collapses it to O(n), one computation per distinct subproblem. A problem without overlapping subproblems, like standard mergesort where every recursive call operates on a genuinely distinct array slice that never recurs, gets zero benefit from memoization, there's nothing to cache, only overhead to add, which is exactly why recognizing overlapping subproblems is the real prerequisite before reaching for this technique.
Quick Reference
| Concept | Meaning |
|---|---|
| Memoization | Caching a subproblem's result so later occurrences are a lookup, not a recomputation |
| Overlapping subproblems | The same subproblem genuinely recurs across different branches of the recursion |
| Optimal substructure | An optimal solution can be built from optimal solutions to its subproblems |
| No overlap → no benefit | Memoization adds only overhead when subproblems never actually repeat |
Syntax
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)Examples
# Without memoization: ~2^n calls, fib(n-2) recomputed repeatedly.
def fib_naive(n):
if n < 2: return n
return fib_naive(n - 1) + fib_naive(n - 2)
# With memoization: O(n), each distinct subproblem solved once.
def fib_memo(n, cache={}):
if n < 2: return n
if n not in cache:
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]Check for overlapping subproblems before reaching for memoization
If the recursive breakdown never revisits the same subproblem twice (like mergesort's array slices), there's nothing for a cache to reuse; memoization adds storage and lookup overhead with zero benefit in that case.
Visual Diagram
Common Mistakes
- Applying memoization to a problem without overlapping subproblems, adding cache overhead for zero actual reuse benefit.
- Writing a naive recursive solution to a problem known to have overlapping subproblems (Fibonacci, edit distance, knapsack) and being surprised by exponential blowup on larger inputs.
- Caching on the wrong key, memoizing by object identity or an incomplete parameter set instead of everything that actually determines a subproblem's result.
- Confusing dynamic programming (caching optimal subproblem solutions) with plain recursion or with greedy algorithms, which don't reconsider earlier choices at all.
Performance
- Memoization trades space (the cache) for time, turning exponential repeated recomputation into linear-or-polynomial time proportional to the number of distinct subproblems, not the number of recursive calls made.
- The size of the cache scales with the number of distinct subproblems, which is itself bounded by the problem's actual parameter space, not by how many times a subproblem happens to recur.
Best Practices
- Confirm a problem actually has overlapping subproblems before reaching for memoization; without that property, it's pure overhead.
- Cache on the complete set of parameters that determine a subproblem's result, not a subset that could cause incorrect cache hits.
- Prefer a language's built-in memoization utility (like
functools.lru_cache) over a hand-rolled cache dictionary when it fits, less code to get wrong. - Consider iterative "tabulation" (building up from the smallest subproblems) as an alternative to recursive memoization when recursion depth on the naive version would be a concern.