Dynamic Programming: Memoization and Tabulation

Dynamic programming (DP) is recursion with a memory. When a recursive function solves the same subproblem more than once, DP says: solve it once, store the answer, and reuse it. That single idea — paired with an honest analysis of the subproblem structure — turns problems that would otherwise be exponential into polynomial-time solutions.

This post introduces DP through Fibonacci, then generalises with a second example. The follow-up post — DP: 8 Classic Problems — applies the technique to a battery of interview favourites.

The two requirements

A problem is a DP problem when it has both:

1. Overlapping subproblems. The same smaller problems are solved multiple times in a naive recursion.
2. Optimal substructure. An optimal solution to the whole problem can be built from optimal solutions to its subproblems.

If only the second holds, you’re often looking at divide-and-conquer (merge sort, quicksort). DP is what you reach for when subproblems repeat.

The motivating example — Fibonacci

The naive recursive Fibonacci is correct but explosive:

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

Here is the call tree for fib(5):

fib(5)
/      

fib(4)        fib(3)
/     \        /     

fib(3)  fib(2)  fib(2)  fib(1)
/   \    /  \    /  

fib(2) f(1) f(1) f(0) f(1) f(0)
/   

fib(1) fib(0)

Look at how many times fib(3), fib(2), fib(1) appear. For fib(n) the call count grows roughly as 1.6^n — useless for n = 50.

Top-down: memoization

The first DP technique is memoization — cache the answer to each subproblem the first time it is computed.

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(50))    # 12586269025

Or, more idiomatically with functools.lru_cache:

from functools import lru_cache

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

Either way, each fib(k) for k from 0 to n is computed exactly once. The runtime drops from exponential to O(n).

This is called top-down because we start from the original problem (fib(n)) and let recursion drive us down to the base cases, caching answers as we return.

Bottom-up: tabulation

The second DP technique is tabulation — build the answer iteratively from the smallest subproblem up to the target. Here is Fibonacci tabulated:

def fib(n):
    if n < 2:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

The table fills left to right. Visually, for fib(6):

index:    0   1   2   3   4   5   6
┌───┬───┬───┬───┬───┬───┬───┐
table:  │ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │
└───┴───┴───┴───┴───┴───┴───┘
▲   ▲   ▲   ▲   ▲
│   │   │   │   │
filled in this order using
table[i] = table[i-1] + table[i-2]

No recursion. No stack. Same answer in O(n) time and O(n) space — which we can drop to O(1) by keeping only the last two values:

def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Both memoization and tabulation are dynamic programming. Use memoization when the recursive shape is natural (some subproblems may not even be needed). Use tabulation when you can evaluate states in a clear order and want to avoid recursion overhead.

How to think in DP

When you face a new problem, work in this order:

1. Identify the state. What single configuration describes a subproblem? For Fibonacci, just the index n. For “longest path in a grid,” maybe (row, col).
2. Write the transition. How does the answer for state s use the answers for smaller states? fib(n) = fib(n-1) + fib(n-2).
3. Identify base cases. Which states have known answers?
4. Choose an order. For tabulation, what order lets every dependency be computed before it is needed?

Most DP bugs come from getting the state wrong (too narrow, too wide) or the order wrong (referring to a cell not yet filled).

A second example — minimum coins

Given coins of denominations [1, 3, 4] and a target amount, what is the minimum number of coins that sums to the target?

The state is n (current remaining amount). The transition: try every coin c and take the best of 1 + min_coins(n - c). The base case: min_coins(0) = 0.

Top-down

from functools import lru_cache

def min_coins(amount, coins=(1, 3, 4)):
    @lru_cache(maxsize=None)
    def f(n):
        if n == 0:
            return 0
        if n < 0:
            return float("inf")
        return 1 + min(f(n - c) for c in coins)
    return f(amount)

print(min_coins(6))    # 2  (3 + 3)

Bottom-up

def min_coins(amount, coins=(1, 3, 4)):
    table = [float("inf")] * (amount + 1)
    table[0] = 0
    for n in range(1, amount + 1):
        for c in coins:
            if c <= n:
                table[n] = min(table[n], table[n - c] + 1)
    return table[amount]

print(min_coins(6))    # 2

The table for amount = 6:

n        : 0  1  2  3  4  5  6
table[n] : 0  1  2  1  1  2  2

table[6] = 2 because 6 = 3 + 3. Each cell looks back at three cells (n-1, n-3, n-4) and picks the smallest plus one.

Memoization vs tabulation — picking one

A common workflow: write the recursive solution, slap @lru_cache on it to confirm correctness, then convert to tabulation if performance or stack depth matters.

Common pitfalls

• Recomputing in memoization. Forgetting to check the cache, or using mutable default arguments wrong. Prefer @lru_cache until you have a reason not to.
• Wrong base case. 0, 1, and “empty input” are easy to confuse. Walk through n = 0 and n = 1 on paper.
• Order of filling. For 2D tables, ask “does row r depend on row r-1? On row r+1?” then loop accordingly.
• Returning the wrong cell. Sometimes the answer is table[n], sometimes max(table), sometimes table[n][m]. Be explicit about what each cell represents.

A small worked example — climbing stairs (full DP walkthrough)

Climbing stairs with 1 or 2 steps:

def climb(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(n - 2):
        a, b = b, a + b
    return b

print(climb(5))    # 8

State: i is the step we’re computing. Transition: ways(i) = ways(i-1) + ways(i-2). Base: ways(1) = 1, ways(2) = 2. Order: left to right.

That four-line analysis is the entire DP playbook. Every problem in the next post fits this template.

Recap

You now know:

• DP applies when a problem has overlapping subproblems and optimal substructure
• Memoization is recursion with a cache — top-down
• Tabulation is iterative — bottom-up, no recursion
• The four-step recipe: state, transition, base case, order
• @lru_cache is a quick way to memoize without writing the cache yourself

Next steps

Time to apply the framework. The next post walks through eight classic DP problems — Climbing Stairs, House Robber, Coin Change, LIS, Word Break, Knapsack, Edit Distance, and LCS — with worked Python solutions and DP tables for each.

→ Next: DP — 8 Classic Problems with Solutions

Questions or feedback? Email codeloomdevv@gmail.com.