Memoization vs tabulation

Dynamic programming (DP) applies when a problem has optimal substructure (the answer can be built from answers to smaller subproblems) and overlapping subproblems (the same smaller subproblems are needed again and again). Plain recursion recomputes them; DP computes each one once.

Memoization is top-down: write the natural recursive function, and store each result in a cache keyed by its arguments, so a repeated call returns instantly. Tabulation is bottom-up: decide an order in which subproblems depend only on earlier ones, then fill an array or table from the base cases up with loops.

Both give the same time complexity, usually (number of states) x (work per state). They differ in style: memoization only computes the states actually needed and is easier to write first; tabulation avoids recursion depth limits, has less overhead, and often lets you shrink memory to the last row or last few values.

1. 1Write a brute-force recursion and notice repeated calls with the same arguments; that is the overlapping-subproblem signal.
2. 2Define the state precisely in words, for example 'f(i) = the answer for the first i items'. The arguments that change between calls are the state.
3. 3Write the recurrence (how f(i) is built from smaller states) and the base cases.
4. 4Memoize: add a cache (a dict or functools.lru_cache). Each state is computed once, so time = states x transitions.
5. 5Or tabulate: create dp sized to the state space, fill base cases, loop in an order where dependencies come first, and return the target cell.
6. 6Optimise space: if dp[i] only uses dp[i-1] and dp[i-2], keep two variables instead of the whole array.

from functools import lru_cache


@lru_cache(maxsize=None)
def fib_memo(n):
    """Top-down: plain recursion plus a cache."""
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


def fib_table(n):
    """Bottom-up: fill the table from the base cases."""
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


def fib_O1(n):
    """Bottom-up keeping only the last two values."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# fib_memo(6) == fib_table(6) == fib_O1(6) == 8

The same recurrence three ways: memoized recursion (O(n) time and stack), a tabulated array (O(n) time and space), and a rolling pair of variables (O(n) time, O(1) space).

Cost: Time = number of states x work per state; space = number of states stored, often reducible with rolling arrays.