Memoization (Top-Down DP)
DSA · Dynamic Programming
Theory
Memoization is a technique where a recursive function stores the result of each subproblem the first time it is computed, and returns the stored result when the same subproblem appears again. It turns exponential recursion into polynomial time whenever subproblems overlap. The classic example is Fibonacci: naive recursion recomputes fib(30) millions of times because fib(n) calls fib(n-1) and fib(n-2), which call the same values again. With a dictionary cache (or Python's functools.lru_cache), each value from 0 to n is computed once, so the time drops from O(2^n) to O(n). Memoization is called top-down dynamic programming because you start from the big problem and recurse down, filling the cache only for subproblems you actually need.
Why we use it
It is the easiest way to convert a correct but slow recursive solution into a fast one, often by adding a single decorator.
When to use it
Use memoization when a problem has a natural recursive definition with overlapping subproblems and you do not need every subproblem. Watch the recursion depth limit (about 1,000 in Python) for very deep problems.
How it works
- solve(state)
- State in memo? Yes: Return memo[state]. No: Compute from smaller states.
- Store result in memo
- Return result
Syntax
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
if base case: return value
return combine(solve(smaller states))Example
import time
from functools import lru_cache
calls = 0
def fib_slow(n):
global calls
calls += 1
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
t = time.perf_counter()
print("slow fib(25) =", fib_slow(25), "calls:", calls)
memo = {}
def fib_memo(n):
if n < 2:
return n
if n not in memo:
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
print("memo fib(90) =", fib_memo(90), "cached values:", len(memo))
@lru_cache(maxsize=None)
def grid_paths(r, c):
if r == 0 or c == 0:
return 1
return grid_paths(r - 1, c) + grid_paths(r, c - 1)
print("paths in 10x10 grid:", grid_paths(10, 10))
print(grid_paths.cache_info())Key points
- Cache results of subproblems so each is computed once
- Top-down: start from the full problem and recurse
- lru_cache adds memoization with one line
- Turns O(2^n) Fibonacci into O(n)