Algorithms · intermediate
Memoization
Memoization caches a function's result by the complete input state so repeated calls for the same state can reuse the result instead of recomputing it.
Why it matters
It collapses overlapping recursive subproblems into one computation per distinct state, often changing exponential work into polynomial work.
Mental model
How to reason about memoization
The first call for a state pays to solve it and records the answer. Every later call with an equivalent state takes the cache shortcut.
Analogy
A reference desk writes down each answered question indexed by its exact wording; an identical question gets the recorded answer, while a materially different question needs new work.
Examples
See the boundary, not just the happy path
Worked example · Fibonacci states
memo[n] = fib(n-1) + fib(n-2)Although the call tree repeats subproblems, only n distinct integer arguments are computed, reducing time to Theta(n).
Worked example · Include all state in the key
cache[(position, remaining_capacity)]Both values affect the answer, so omitting either could return a result computed for a different subproblem.
Avoid · Cache an impure result
memoize(readCurrentWeather(city)) foreverThe output depends on time and external state, not only city. Reusing it indefinitely changes the function's intended behavior.
Common mistakes
Misconceptions to remove early
Using an incomplete cache key
Every input that can affect the result belongs in the key. Missing context creates plausible but incorrect cache hits.
Ignoring cache lifetime
Memoization retains results and can grow without bound or serve stale values. Bound, expire, or scope the cache when state is large or changing.
Quick check
Can you predict the result?
1. When is a memoized cache hit valid?
- • When the key captures every input that can affect a deterministic result
- • Whenever the function name is the same
- • Only when the previous call was slow
2. Why does memoized Fibonacci avoid exponential recomputation?
Keep building