Memoization & TabulationMemoisation and tabulation

01Why it exists

Reach for it when you see:Overlapping subproblems, the same arguments computed many times over, repeated nodes in the recursion tree, how many ways, minimum or maximum, pure functions, @cache, recursion too deep, top-down, bottom-up.

02The core idea

Write Fibonacci straight from the definition as fib(n) = fib(n−1) + fib(n−2) and the recursion tree sprouts duplicates everywhere: computing fib(6) works out fib(2) in full five separate times. The problem is not recursion itself, it is that nothing remembers what has already been computed. Memoisation is top-down: keep the original recursion and add a cache keyed by the arguments, looking it up on the way in and storing the result on the way out. Tabulation is bottom-up: no recursion at all. Work out what depends on what, then start from the base cases and loop through dp[0], dp[1], dp[2]… in order. Both solve the same set of subproblems with the same transition; they differ only in who decides the order. Memoisation lets the recursion ask for what it needs, tabulation has you lay the order out in advance.

There is one precondition: the function must be pure, its return value fixed by its arguments alone, depending on no global variable and on nothing about how you got here. Only then is the cached answer guaranteed to still be correct the second time the same arguments come up. Those arguments are the DP state, and the cache key has to carry everything that affects the answer — leave one thing out and two different problems get treated as the same one. Tabulation's correctness rests on fill order instead: by the time you compute dp[i], every cell it depends on must already be filled, which means filling in topological order of the subproblem dependencies. Induct on i: the base cases are correct, and every cell is built only from cells that are already correct, so the whole table is correct. If the dependencies contain a cycle neither approach works, and memoisation recurses forever.

The general complexity formula is number of states × cost per transition. Fibonacci has n+1 states at O(1) each, so O(n). Compare that with plain recursion: the call count satisfies c(n) = c(n−1) + c(n−2) + 1, which solves to 2·fib(n+1) − 1 and grows roughly as 1.618ⁿ, so n = 40 already costs over 330 million calls. The memoised version makes 2n − 1 calls, of which n+1 do real work and the rest are cache hits. For space, memoisation needs an O(n) cache plus an O(n)-deep call stack; tabulation needs only the O(n) array, and since dp[i] reads just the previous two cells you can roll two variables and get down to O(1).

How to choose: memoisation is the easiest to write — brute-force recursion plus three lines — and it only ever computes states you actually reach, which makes it the only option when the state space is enormous but very little of it gets visited. The price is recursion depth: Python's default limit is 1000 frames, so fib_memo(5000) raises RecursionError outright. Tabulation has no recursion, a smaller constant factor, and makes space compression easy, but you have to work out the fill order yourself and every state gets computed. Common traps: writing memo={} as a Python default argument, so a fresh input still reads the previous one's answers; @cache arguments must be hashable, so lists become tuples or you switch to indices as the state; C++'s long long overflows at fib(93). How this differs from the neighbouring lessons: in divide and conquer the subproblems do not overlap (merge sort's two halves are disjoint), so a cache buys nothing; backtracking enumerates every path, but when the question is only "how many" or "what is the best", and where you can go next depends only on the current state, it can be rewritten as memoisation. The next lesson on one-dimensional DP treats tabulation plus space compression as the default.

03The algorithm

1. 1Write the brute-force recursion first, and say exactly what the function means: ways(i) returns "how many ways there are to reach step i". The arguments are the state, and the base cases go at the very top.
2. 2Check two things: the same arguments show up more than once in the recursion tree (overlapping subproblems), and the return value depends on the arguments alone. Caching is only safe when nothing depends on a global variable or on the path taken to get here.
3. 3Memoisation: create a dict or array keyed by the state (use −1 for "not computed yet"). Look it up on entry and return straight away on a hit; otherwise run the original recursion and store the result before returning it. In Python you can simply add @cache.
4. 4Tabulation: replace the function with an array dp, fill in the base cases, then loop in an order that computes every dependency first, applying the same transition to each cell. If dp[i] depends on smaller indices, let i run from small to large.
5. 5Space compression: look at how many cells the transition actually reads. If it only reads the previous k, roll k variables instead and space drops from O(n) to O(1).
6. 6Estimate number of states × cost per transition to confirm you are inside the time limit. Switch to tabulation when the recursion could run tens of thousands of frames deep; stay with memoisation when the state space is enormous but only a small part of it is ever reached.

04Interactive demo

Computing fib(6), with the tree writing f(n) for fib(n). The whole recursion tree starts faded and lights up in call order as you press "Next": blue is the call in progress, grey is a base case reached for the first time. "Plain recursion" mode takes 25 calls, and the 18 yellow ones are subproblems being recomputed — the entire f(4) and f(3) subtrees get expanded all over again. Switch to "Memoised" and the same problem takes only 11 calls; green marks a cache hit, and the subtree below it is never expanded. The cards under the tree count the calls in each mode, and the small table beside them shows the gap at n = 6, 10, 20 and 30: by n = 30 it is 2,692,537 calls against 59.

05Code

The same fib written four ways — plain recursion, memoisation (a hand-written cache and @cache), tabulation, and the two-variable compressed version — so you can see exactly what each step changes; the C++ cache is an array that uses −1 for "not computed yet". Then the stair climb with a choice of step sizes shows the same transformation applied to a transition with several options, and the Python memoised version deliberately puts @cache inside the function so that different steps never share a cache.

from functools import cache


# 1. Plain recursion: straight from the definition. About 1.618ⁿ calls, so n = 40 needs over 300 million
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# 2. Memoisation (top-down): the original recursion plus a cache keyed by the arguments
def fib_memo(n, memo=None):
    if memo is None:                       # never write memo={}: a default is built once and shared by every call
        memo = {}
    if n in memo:                          # check the cache first
        return memo[n]
    if n <= 1:
        result = n                         # base case
    else:
        result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    memo[n] = result                       # store it before returning
    return result


@cache                                     # the standard library does the same job: the arguments are the cache key
def fib_cached(n):
    return n if n <= 1 else fib_cached(n - 1) + fib_cached(n - 2)


# 3. Tabulation (bottom-up): no recursion, fill upward starting from the base cases
def fib_table(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):              # when dp[i] is computed, dp[i-1] and dp[i-2] are already filled in
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


# 4. Space compression: dp[i] only reads the previous two cells, so two variables are enough. O(1) space
def fib_rolling(n):
    a, b = 0, 1                            # a = fib(i), b = fib(i+1)
    for _ in range(n):
        a, b = b, a + b
    return a


# Generalised: climbing n stairs where each move is any step size in steps (steps = [1, 2] is LeetCode 70)
def climb_memo(n, steps):
    @cache                                 # the cache lives inside the function: every climb_memo call gets a fresh one
    def ways(i):                           # the state is just i; steps is fixed for this call, so it stays out of the key
        if i == 0:
            return 1                       # already standing on step 0: one way (do nothing)
        return sum(ways(i - s) for s in steps if s <= i)
    return ways(n)


def climb_table(n, steps):
    dp = [1] + [0] * n                     # dp[i] = number of ways to reach step i
    for i in range(1, n + 1):
        dp[i] = sum(dp[i - s] for s in steps if s <= i)
    return dp[n]


if __name__ == "__main__":
    print(fib_naive(20), fib_memo(20), fib_cached(20))    # 6765 6765 6765
    print(fib_table(90), fib_rolling(90))                 # 2880067194370816120 2880067194370816120
    print(climb_memo(10, [1, 2]), climb_table(10, [1, 2]))          # 89 89
    print(climb_memo(10, [1, 3, 5]), climb_table(10, [1, 3, 5]))    # 47 47
    print(len(str(fib_table(5000))))                      # 1045 (fib(5000) has 1045 digits)
    # fib_memo(5000) raises RecursionError: deeper than Python's default limit of 1000

06Practice

• LeetCode 509Fibonacci Number (write it three times: memoised, tabulated, rolling variables)Easy
• LeetCode 70Climbing Stairs (turn the brute-force recursion into a table)Easy
• LeetCode 1137N-th Tribonacci Number (roll three variables)Easy
• LeetCode 377Combination Sum IV (the generalised stair climb from the code)Medium
• LeetCode 2140Solving Questions With Brainpower (fill the table back to front)Medium
• LeetCode 1553Minimum Number of Days to Eat N Oranges (n up to 2×10⁹, memoisation only)Hard