AdvancedDynamic Programming
Memoization: recursion that remembers
Write the natural recursion first, then cache each result. Exponential time often drops to polynomial with one decorator.
The idea
Many recursive solutions recompute the same inputs again and again. Fibonacci recursion calls fib(3) many times inside fib(6). Storing each answer the first time turns repeated calls into lookups.
Top-down (memo) is often easier to get right than bottom-up tables: write the recursion, add a cache, done.
Worked example
Coin Change: fewest coins for 11 with coins [1, 2, 5]
- best(11) = 1 + min(best(10), best(9), best(6))
- Without a cache, best(5) is recomputed many times; with one, each amount 0..11 is solved once.
- Answer 3 (5 + 5 + 1).
In code (Python)
from functools import cache
def coin_change(coins, amount):
@cache
def best(rest):
if rest == 0:
return 0
if rest < 0:
return float("inf")
return 1 + min(best(rest - c) for c in coins)
answer = best(amount)
return -1 if answer == float("inf") else answerO(amount × coins) time, O(amount) space for the cache.
How to spot it
- Your recursion has overlapping subproblems (the same arguments repeat).
Common mistakes
- Caching on mutable arguments like lists (they aren't hashable).
- Deep recursion on large inputs: Python's default limit is about 1000 frames.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →