Learn how top-down dynamic programming caches recursive results to avoid recomputation.

Memoization

Memoization is the top-down approach to dynamic programming. You write the natural recursive solution, then add a cache — a dictionary or array that stores every result you have already computed. Before computing anything, check the cache first. If the result is already there, return it immediately.

Memoizationtop-down · fib(7)

call stack

empty

memo cache

fib_memo.py

def fib(n, memo={}):

if n in memo: return memo[n]

if n <= 1: return n # base case

result = fib(n-1) + fib(n-2)

memo[n] = result; return result

# O(n) — each n computed once

Call fib(7) — compute with memoization

step 0/22

Fibonacci without memoization — O(2ⁿ)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(40)   # takes seconds — billions of calls
fibonacci(50)   # takes minutes

The call tree for fibonacci(6) has 25 nodes — many computed multiple times. fibonacci(50) would have over 2 trillion calls.

Fibonacci with memoization — O(n)

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]   # already computed — return immediately

    if n <= 1:
        return n

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]


print(fibonacci(50))    # 12586269025 — instant
print(fibonacci(100))   # 354224848179261915075 — still instant

Each value from 0 to n is computed exactly once and then cached. Total work: O(n).

Using Python's @lru_cache

Python's functools.lru_cache adds memoization automatically — no manual dictionary needed:

from functools import lru_cache

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


print(fibonacci(100))   # 354224848179261915075

maxsize=None means unlimited cache size. The decorator handles all the caching logic transparently.

More complex example — climbing stairs

Given n stairs, you can climb 1 or 2 stairs at a time. How many distinct ways are there to reach the top?

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs(n):
    if n <= 1:
        return 1   # 0 or 1 stair — exactly one way
    if n == 2:
        return 2   # (1+1) or (2)

    # at each step, came from n-1 or n-2
    return climb_stairs(n - 1) + climb_stairs(n - 2)


for i in range(1, 8):
    print(f"n={i}: {climb_stairs(i)} ways")

# n=1: 1   n=2: 2   n=3: 3   n=4: 5   n=5: 8   n=6: 13   n=7: 21

Notice the same recurrence as Fibonacci! The number of ways to climb n stairs equals ways(n-1) + ways(n-2).

Coin change with memoization

Given coins and a target amount, what is the minimum number of coins needed?

from functools import lru_cache

def coin_change(coins, amount):
    @lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0   # no coins needed
        if remaining < 0:
            return float("inf")   # impossible

        min_coins = float("inf")
        for coin in coins:
            result = dp(remaining - coin)
            if result != float("inf"):
                min_coins = min(min_coins, result + 1)

        return min_coins

    result = dp(amount)
    return result if result != float("inf") else -1


print(coin_change([1, 5, 10, 25], 36))   # 3  → 25+10+1
print(coin_change([2], 3))               # -1  → impossible

When memoization shines

Memoization is especially natural when:

The recursive structure is already clear in your head
The subproblems are not all needed (sparse recursion — only some states are ever reached)
The order of solving subproblems is complex or hard to determine bottom-up

A common interview approach: start with the naive recursive solution to verify correctness, then add @lru_cache in one line to get O(n) performance. This is often cleaner and faster to write than tabulation during an interview, as long as recursion depth is not a concern.

Complexity

	Time	Space
Without memo	O(2ⁿ)	O(n) call stack
With memo	O(n)	O(n) cache + O(n) call stack

The cache uses O(n) space but eliminates the exponential recomputation entirely.

Memoization

On this page