Memoization (Top-Down DP)

Memoization is the technique of caching the results of expensive function calls so that when the same inputs occur again, you return the stored answer instead of recomputing it. It is the “top-down” style of dynamic programming: you write the natural recursive solution to a problem, and then add a cache that remembers every subproblem you have already solved. The payoff is dramatic — problems that would otherwise take exponential time, like naive recursive Fibonacci, collapse to linear or polynomial time once repeated work is eliminated.

Overview / How It Works

Many recursive problems break into smaller subproblems that overlap: the same subproblem gets solved over and over again as part of different branches of the recursion tree. Computing the nth Fibonacci number recursively is the classic illustration. fib(5) calls fib(4) and fib(3). But fib(4) itself calls fib(3) again — a second, completely redundant computation of the exact same value. As n grows, the number of redundant recomputations explodes, because the recursion tree has roughly 2^n nodes even though there are only n distinct subproblems (fib(0) through fib(n)).

Memoization fixes this by keeping a cache — typically a dict — keyed on the function’s arguments (the “state”). Before doing any real work, the function checks: have I already solved this exact subproblem? If yes, return the cached answer immediately. If no, do the work, store the answer in the cache, and then return it. Because every distinct state is computed at most once, the total work becomes proportional to the number of distinct states, not the number of times a state is *reached* by the recursion.

Two conditions make a problem a good fit for memoization, and they are the two hallmarks of dynamic programming in general:

  • Overlapping subproblems — the same smaller inputs recur many times across the recursion (Fibonacci, counting paths, edit distance).
  • Optimal substructure — the answer to a problem can be built directly from the answers to its subproblems (the best way to reach step n depends only on the best ways to reach step n-1 and n-2).

If a recursive problem does not have overlapping subproblems (each subproblem is only ever visited once, like a plain binary search or a simple tree traversal), adding a cache buys you nothing but memory and lookup overhead.

Time and Space Complexity

The complexity of a memoized solution is governed by a simple rule: time is (number of distinct states) × (work done per state, ignoring recursive calls), and space is (size of the cache) + (maximum recursion depth).

Approach Time Space Why
Naive recursive Fibonacci (no cache) O(2^n) O(n) The call tree branches into two calls at every level; the same values are recomputed exponentially many times. Space is just the recursion stack depth.
Memoized Fibonacci (1D state n) O(n) O(n) There are only n + 1 distinct states (0 through n); each is computed once in O(1) work beyond its recursive calls. The cache holds n + 1 entries and the call stack reaches depth n.
Memoized 2D DP (e.g. Longest Common Subsequence on strings of length n and m) O(n × m) O(n × m) The state is a pair (i, j), giving n × m distinct states, each computed once in O(1) work. The cache stores one entry per state; the recursion stack depth is O(n + m).

The general lesson: to find the complexity of a top-down DP solution, count how many distinct argument combinations (states) the cache key can take, and multiply by the non-recursive work inside one call.

Examples

Example 1: Naive recursion — the problem memoization solves

Before fixing anything, it helps to see the disease. This version counts how many times the function is actually invoked while computing fib(10):

def fib_naive(n: int) -> int:
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


call_count = 0
result = fib_naive(10)
print(f"fib(10) = {result}")
print(f"calls made = {call_count}")

Output:

fib(10) = 55
calls made = 177

fib(10) is correctly 55, but it took 177 function calls to get there — even though there are only 11 distinct values (fib(0) through fib(10)) that ever need to be computed. Every value below the top is recomputed many times over.

Example 2: Adding memoization with a dict cache

def fib_memo(n: int, cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}
    global call_count
    call_count += 1
    if n in cache:
        return cache[n]
    if n <= 1:
        cache[n] = n
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


call_count = 0
result = fib_memo(10)
print(f"fib(10) = {result}")
print(f"calls made = {call_count}")

Output:

fib(10) = 55
calls made = 19

Same answer, 177 calls down to 19. The cache is created once (when cache is None) and then threaded through every recursive call so all of them share it. Every value is checked against the cache first; once a value has been computed, every later request for it is an O(1) lookup instead of a fresh recursive descent.

Example 3: functools.lru_cache — letting the standard library do it

For pure functions (same input always gives the same output, no side effects) with hashable arguments, Python’s functools.lru_cache decorator memoizes automatically — no manual dict required:

from functools import lru_cache


@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)


result = fib_lru(35)
print(f"fib(35) = {result}")
print(f"cache info: {fib_lru.cache_info()}")

Output:

fib(35) = 9227465
cache info: CacheInfo(hits=33, misses=36, maxsize=None, currsize=36)

fib_lru(35) returns instantly because of the cache — the naive version would need over 29 billion calls. cache_info() confirms it: only 36 misses (one per distinct value of n from 0 to 35) and 33 hits (cached values reused instead of recomputed). With lru_cache, a cache hit returns straight from the cache without ever re-entering the function body, so hits don’t trigger further recursion at all.

Example 4: A more realistic case — Longest Common Subsequence

Real interview problems usually have a multi-part state. Here the state is a pair of indices (i, j) into two strings, so the cache key is a tuple:

def lcs_length(text1: str, text2: str) -> int:
    cache: dict[tuple[int, int], int] = {}

    def solve(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if (i, j) in cache:
            return cache[(i, j)]
        if text1[i] == text2[j]:
            result = 1 + solve(i + 1, j + 1)
        else:
            result = max(solve(i + 1, j), solve(i, j + 1))
        cache[(i, j)] = result
        return result

    return solve(0, 0)


result = lcs_length("abcde", "ace")
print(f"LCS length = {result}")

Output:

LCS length = 3

The longest common subsequence of "abcde" and "ace" is "ace" itself (length 3) — every character of "ace" appears in "abcde" in the same relative order. The inner solve function is a closure that captures cache, text1, and text2, which keeps the cache scoped to a single call of lcs_length rather than leaking across unrelated calls.

How It Works Step by Step

Tracing fib_memo(5) call by call shows exactly where the savings come from. Calls are numbered in the order they happen; “HIT” means the value was already in the cache and no further recursion happened.

# Call What happens
1 fib_memo(5) miss — calls fib_memo(4) then fib_memo(3)
2 fib_memo(4) miss — calls fib_memo(3) then fib_memo(2)
3 fib_memo(3) miss — calls fib_memo(2) then fib_memo(1)
4 fib_memo(2) miss — calls fib_memo(1) then fib_memo(0)
5 fib_memo(1) base case — caches 1
6 fib_memo(0) base case — caches 0; call 4 now caches fib_memo(2) = 1
7 fib_memo(1) HIT — returns cached 1; call 3 now caches fib_memo(3) = 2
8 fib_memo(2) HIT — returns cached 1; call 2 now caches fib_memo(4) = 3
9 fib_memo(3) HIT — returns cached 2; call 1 now caches fib_memo(5) = 5

Notice the shape: the recursion first plunges all the way down the “n - 1” branch to the base cases, filling the cache as it unwinds. By the time the “n - 2” branch of any call is reached, that value has almost always already been computed and cached from the deeper branch, so it resolves in a single O(1) lookup instead of a fresh recursive descent. That’s why the call count grows linearly (2n - 1 calls for Fibonacci) instead of exponentially.

Common Mistakes

Mistake 1: mutable default argument used as the cache

Python evaluates default argument values once, when the function is defined — not on every call. A mutable default like cache={} is therefore the same dict object shared across every call to the function for the lifetime of the program. If the cache key doesn’t fully capture everything that affects the answer, later calls can silently read stale, wrong values left over from an earlier, unrelated call:

def count_ways(n: int, blocked: set[int], cache={}) -> int:
    # BUG: mutable default argument — this same dict is reused
    # across every call to count_ways, forever.
    if n in cache:
        return cache[n]
    if n == 0:
        return 1
    if n in blocked:
        return 0
    ways = 0
    if n - 1 >= 0:
        ways += count_ways(n - 1, blocked, cache)
    if n - 2 >= 0:
        ways += count_ways(n - 2, blocked, cache)
    cache[n] = ways
    return ways


first = count_ways(4, {2})
second = count_ways(4, {3})
print(first, second)

The cache is keyed only by n, but the actual answer also depends on blocked. The first call populates the shared cache using blocked={2}. The second call, with a different blocked={3}, reuses that same dict — so any step number it already computed comes back from the stale cache instead of being recomputed for the new blocked set, giving a wrong answer with no error raised at all. The fix is to default to None and create a fresh cache inside the function (or make the cache key include everything the answer depends on):

def count_ways(n: int, blocked: set[int], cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n == 0:
        return 1
    if n in blocked:
        return 0
    ways = 0
    if n - 1 >= 0:
        ways += count_ways(n - 1, blocked, cache)
    if n - 2 >= 0:
        ways += count_ways(n - 2, blocked, cache)
    cache[n] = ways
    return ways


first = count_ways(4, {2})
second = count_ways(4, {3})
print(f"blocked={{2}}: {first} ways")
print(f"blocked={{3}}: {second} ways")

Output:

blocked={2}: 1 ways
blocked={3}: 2 ways

Now each top-level call gets its own fresh cache, so the two calls no longer interfere with each other.

Mistake 2: forgetting the base case

Every recursive memoized function needs a base case that stops the recursion without making another recursive call. Omit it, and the function recurses forever — there is nothing a cache can do about it, because the cache is only ever populated after a call returns, and a call that never returns never populates anything:

def fib_broken(n: int) -> int:
    return fib_broken(n - 1) + fib_broken(n - 2)  # missing base case!


print(fib_broken(10))

This keeps calling itself with smaller and smaller (and eventually negative) values of n, with no condition ever stopping it, until Python’s recursion limit is hit and it crashes with RecursionError: maximum recursion depth exceeded. The fix is simply to restore the stopping condition before doing any recursive work:

def fib_fixed(n: int, cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_fixed(n - 1, cache) + fib_fixed(n - 2, cache)
    return cache[n]


print(f"fib(10) = {fib_fixed(10)}")

Output:

fib(10) = 55

Best Practices

  • Reach for memoization when a recursive solution has both overlapping subproblems and optimal substructure. If every subproblem is only ever visited once, a cache adds overhead for no benefit.
  • Make sure the cache key captures everything the answer depends on. A key that’s missing part of the state (like the blocked set above) causes silently wrong results, not crashes — the hardest kind of bug to catch.
  • Prefer functools.lru_cache for pure functions with hashable arguments — it’s tested, fast, and gives you cache_info() for free. Write your own dict-based cache when arguments are unhashable (like lists), when you need to inspect/clear the cache manually, or when the cache must be scoped to a single call instead of persisting across the whole program.
  • Never default a cache parameter to a mutable object (cache={}). Default it to None and create the cache inside the function, so each independent top-level call starts clean.
  • Watch Python’s default recursion limit (around 1000 frames). Deep memoized recursion on large inputs can still raise RecursionError even though the cache prevents redundant work — if that’s a risk, rewrite the same recurrence as bottom-up tabulation, which uses no call stack at all.
  • Top-down memoization is often easier to write than bottom-up tabulation because you just write the natural recursive definition and let the cache handle “already solved” for you — but tabulation can be more space-efficient, since you can often keep only the last row or two of results instead of every state ever seen.

Practice Exercises

  • Triple-step climbing stairs: write a memoized function that counts the number of distinct ways to climb n stairs when you can take 1, 2, or 3 steps at a time. Hint: base cases are ways(0) = 1, ways(1) = 1, ways(2) = 2, and the recurrence sums the three previous states.
  • Minimum coin change: given a list of coin denominations and a target amount, use top-down memoization to find the minimum number of coins needed to make that amount exactly, returning -1 if it’s impossible. Hint: the state is the remaining amount, and for each coin you can either use it (reducing the remaining amount) or skip it.
  • Word break: given a string and a set of dictionary words, use memoization to determine whether the string can be split into a sequence of dictionary words. Hint: the state is the starting index into the string; memoize on “can the remaining suffix starting at index i be segmented?”

Summary

  • Memoization is top-down dynamic programming: write the natural recursive solution, then cache each subproblem’s result so it’s computed only once.
  • It applies when a problem has overlapping subproblems and optimal substructure; without overlap, caching adds overhead for no gain.
  • Naive recursive Fibonacci is O(2^n) time; memoized Fibonacci is O(n) time and O(n) space, because there are only n + 1 distinct states.
  • Multi-dimensional states (like the (i, j) pairs in Longest Common Subsequence) cost O(states) = O(n × m) time and space — count distinct states to find the complexity of any top-down DP.
  • functools.lru_cache memoizes pure, hashable-argument functions automatically; use a manual dict cache for unhashable state or finer control.
  • Never use a mutable default argument as a cache, and never omit the base case — both are silent-failure or crash-prone bugs that are easy to avoid once you know to look for them.