Memoization is simple: before computing a result, check if you've computed it before. If yes, return the cached value instantly. If no, compute it, store it, return it. That's the entire technique.
It transforms recursive algorithms with overlapping subproblems from exponential to polynomial time. Fibonacci goes from O(2ⁿ) to O(n). Coin change goes from exponential to O(n·k). It's the gateway concept to dynamic programming.
Every unique input is computed exactly once. All subsequent calls with that input return the cached result in O(1). No redundant work.
Memoization only helps when the same subproblem recurs. fib(3) is called 3 times in fib(5) — that's 3 overlapping subproblems. Without a cache, all 3 run fully.
Memoization is top-down dynamic programming — start from the top (fib(n)) and recurse down, caching as you go. Bottom-up DP fills a table from the smallest case upward.
Memoization pays O(n) space (the cache) to save exponential time. Always ask: what does the cache store, and how large can it get?
TIPWatch the call counter in the naive run. For fib(7) it reaches 41. In the memoised run it stops at 8. Same answer, same algorithm structure — the only difference is one Map lookup at the start of each call.
COLOUR LEGEND
Cache hit — instant return ⚡