Memoization

Caching · Overlapping Subproblems

1:00

How caching the results of recursive calls eliminates redundant recomputation and collapses exponential time into linear time.

By the end, you can

Define memoization and explain the four-step cache pattern (check, compute, store, return).
Trace the naive Fibonacci recursion tree for fib(5) and count its 15 calls and redundant subproblems.
Fill in a memoization cache table from base cases up using the fib recurrence.
State the time and space complexity of memoized Fibonacci and explain why each subproblem is solved exactly once.
Apply @lru_cache in Python and explain what maxsize controls.
Identify when memoization is inappropriate: impure functions, non-overlapping subproblems, unhashable keys.
Contrast memoization (top-down, lazy, call-stack overhead) with tabulation (bottom-up, iterative, potential O(1) space).

Up next in Algorithms & Graph Algorithms