Dynamic Programming: Memoization vs Tabulation and How to Spot a DP Problem

By 0xmote · May 25, 2026 · 14 min read · Updated Sep 29, 2026 Intermediate Tutorial

Key takeaways

Dynamic programming is recursion that refuses to solve the same subproblem twice. This guide explains when that is valid (optimal substructure and overlapping subproblems), how to define the state so the recurrence writes itself, how top-down memoization and bottom-up tabulation differ in practice, and the recursion-limit, table-size and reconstruction bugs that fail DP submissions.

Introduction

Dynamic programming (DP) has a reputation for being the hardest topic in interview preparation, but the core idea is small: if a recursive solution keeps solving the same subproblems, store each answer the first time and look it up afterwards. The difficulty is not the caching. It is deciding what a “subproblem” is, which is to say defining the state, and then filling the table in an order where every value you need already exists.

This article covers those fundamentals with deliberately small problems: Fibonacci, climbing stairs, house robber, grid paths and coin change. The larger families (knapsack variants, LCS, LIS, edit distance, interval DP) are covered in DP Patterns, and worked practice problems in DP Practice Problems.

Why Caching Works: The Two Conditions

Overlapping subproblems

The naive recursive Fibonacci is the standard example because the waste is easy to see:

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

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  └─ fib(1)
│  └─ fib(2)      ← computed again
└─ fib(3)         ← the whole subtree again
   ├─ fib(2)
   └─ fib(1)

There are only n + 1 distinct subproblems, fib(0) to fib(n), but the call tree grows exponentially, roughly by a factor of 1.618 per level. Counting calls, fib_naive(30) makes 2,692,537 of them to compute 832,040. Every one of those calls answers one of just 31 distinct questions.

Optimal substructure

Caching only helps if the answer to a subproblem does not depend on how you got there. For “minimum cost to reach cell (r, c)”, the best way to reach (r, c) is the same no matter where you are going next, so its answer can be reused. That property is optimal substructure.

It fails more often than people expect. The longest simple path between two vertices in a graph has no optimal substructure: the best path from A to B may reuse vertices that the best path from B to C needs, so you cannot combine the two sub-answers. When the answer to a subproblem depends on history (which items were used, which cells were visited), that history has to become part of the state, and if the history is large, DP stops being efficient. That is the moment to reach for backtracking or a different model.

The complexity rule

Once both conditions hold, the running time of a DP is:

number of states × work per state (the number of transitions)

Fibonacci has n states with O(1) work each, so O(n). A grid with R × C cells and two incoming moves is O(RC). Coin change with amount A and k coin types is O(A·k). If you can state this product before you write code, you know whether the solution fits the limits.

Top-Down: Memoization

Top-down DP is the recursive solution with a cache in front of it. It follows the recurrence directly and only computes states that are actually reachable.

def fib_memo(n, memo=None):
    if memo is None:          # not memo={}: see below
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(40))  # 102334155

The memo=None line fixes a classic Python trap. A default argument like memo={} is created once, when the function is defined, and shared by every call. For Fibonacci that happens to be harmless, but in a problem where the function is called once per test case with different inputs, answers from the previous test leak into the next one.

functools.lru_cache and cache

The standard library does the bookkeeping for you:

from functools import lru_cache

@lru_cache(maxsize=None)   # or @functools.cache on Python 3.9+
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

print(fib_cached(100))  # 354224848179261915075

Three things to know before relying on it:

Arguments must be hashable. Passing a list raises TypeError: unhashable type: 'list'. Pass indices into the list instead of slices of it, or convert to a tuple.
The cache outlives the call. A decorated function defined at module level keeps its cache across test cases. If the function closes over per-test data, define it inside the solving function or call fib_cached.cache_clear().
Memoization does not reduce recursion depth. Computing f(n) from an empty cache still goes n levels deep before anything is cached.

The third point is the one that fails submissions. I tested it on CPython 3.11 by searching for the largest n that runs with the default recursion limit of 1000: the hand-written dict version worked up to n = 999, but the lru_cache version only up to n = 499, because each level passes through the cache wrapper and counts roughly twice. So a memoized solution that looks correct for n = 100 raises RecursionError at n = 1000, which is a perfectly ordinary input size.

I have lost a submission to exactly this: a clean @cache recurrence, correct on every sample, and a runtime error on the largest test. There are three ways out. Raising sys.setrecursionlimit sometimes works but can crash the interpreter on deep inputs, because the real limit is the C stack. Warming the cache in increasing order (call f(200), f(400), and so on before f(n)) keeps each call shallow. The robust fix is to convert to bottom-up.

Bottom-Up: Tabulation

Bottom-up DP fills a table from the smallest subproblems to the largest, so every value a state depends on is already computed when it is needed. There is no recursion, so no depth limit, and the loop is usually faster than the equivalent recursive calls.

def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)   # n + 1 entries: dp[0] .. dp[n]
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_dp(100))  # 354224848179261915075

The two things you must get right are the evaluation order (every dependency of dp[i] has a smaller index, so a forward loop works) and the table size. [0] * n with dp[n] as the answer is an IndexError, and the “fix” of returning dp[n - 1] usually produces an answer for a different question.

Keeping only what the recurrence reads

dp[i] only reads the previous two entries, so the table can shrink to two variables:

def fib_optimized(n):
    prev2, prev1 = 0, 1        # fib(0), fib(1)
    for _ in range(n):
        prev2, prev1 = prev1, prev1 + prev2
    return prev2

print(fib_optimized(100), fib_optimized(0), fib_optimized(1))
# 354224848179261915075 0 1

This is easy in bottom-up and awkward in top-down, which is the main practical reason to prefer tabulation once the recurrence is known. The trade-off: once you keep only the last row, you can no longer reconstruct which choices led to the answer, so do the space optimization only when you need just the value.

Choosing between them

	Top-down (memoization)	Bottom-up (tabulation)
Written from	The recurrence, directly	The recurrence plus an evaluation order
States computed	Only reachable ones	All of them
Recursion depth	Up to the longest chain of states	None
Space optimization	Hard	Easy (keep last row/rows)
Good fit	Sparse or irregular state spaces, first draft	Large inputs in Python, tight memory limits

My own workflow is to write the top-down version first, because it is the recurrence with a cache and easy to check against a brute force. If the input size makes the depth risky, I convert it to a loop, and the memo dictionary tells me which order the loop needs.

Defining the State

Almost every wrong DP I have debugged came down to a state that meant one thing in the recurrence and another thing in the base case. Before writing code, write one sentence: “dp[i] is …”. Then derive everything from that sentence.

Climbing stairs: pick a definition that makes the base case obvious

You climb n stairs taking 1 or 2 steps at a time. How many distinct ways are there?

Definition: ways[i] is the number of ways to stand on stair i. Your last move was either a 1-step from stair i - 1 or a 2-step from stair i - 2, and those sets of ways do not overlap, so ways[i] = ways[i-1] + ways[i-2]. The base case follows from the definition: there is exactly one way to stand on stair 0, by not moving.

def climb_stairs(n):
    ways = [0] * (n + 1)
    ways[0] = 1
    for i in range(1, n + 1):
        ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
    return ways[n]

print(climb_stairs(1), climb_stairs(2), climb_stairs(3), climb_stairs(5))  # 1 2 3 8

Starting from ways[0] = 1 means no special cases for n = 1 or n = 2, which is where hand-written base cases like if n <= 2: return n tend to break when the step sizes change.

House robber: “first i items” vs “ending at i”

You cannot rob two adjacent houses; maximize the total. Two definitions are possible, and mixing them is the common bug:

best[i] = best total using the first i houses. Then best[i] = max(best[i-1], best[i-2] + nums[i-1]), and the answer is best[n].
end[i] = best total if house i is robbed. Then the answer is max(end), not end[n-1].

Tracking two running values, “best if I take this house” and “best if I skip it”, is the space-optimized form of the first definition:

def rob(nums):
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

print(rob([2, 7, 9, 3, 1]))  # 12  (2 + 9 + 1)
print(rob([2, 1, 1, 2]))     # 4   (2 + 2)
print(rob([]))               # 0

Grid paths: pad the table instead of special-casing edges

Minimum path sum moves right or down from the top-left to the bottom-right cell. Definition: dp[r][c] is the minimum sum of a path ending at cell (r, c). Instead of separate loops for the first row and first column, pad the table with one extra row and column of infinity, and give the start a single zero entry to come from:

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    INF = float("inf")
    dp = [[INF] * (cols + 1) for _ in range(rows + 1)]  # dp[r][c] <-> grid[r-1][c-1]
    dp[0][1] = 0                                         # entry point for the start cell
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            dp[r][c] = grid[r - 1][c - 1] + min(dp[r - 1][c], dp[r][c - 1])
    return dp[rows][cols]

print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7  (1→3→1→1→1)
print(min_path_sum([[5]]))                              # 5
print(min_path_sum([[1, 2, 3]]))                        # 6

The padding shifts every index by one, which is a trade: fewer edge cases in the loop, but you must remember that dp[r][c] corresponds to grid[r-1][c-1]. Write that mapping as a comment, as above, because it is exactly the kind of off-by-one that is invisible when reading the code later.

Getting the Answer, Not Just the Number

Coin change, with reconstruction

Given coin denominations and an amount, find the fewest coins that make the amount, or -1 if impossible. Definition: dp[a] is the fewest coins that sum to exactly a. The last coin used is some c, so dp[a] = 1 + min(dp[a - c]) over coins c ≤ a, with dp[0] = 0. Infinity marks amounts that cannot be made, so they never win a min.

Interviewers often follow up with “which coins?”. Recording the choice that produced each value lets you walk back from the answer:

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount     # amount + 1 entries
    choice = [-1] * (amount + 1)  # last coin used for each amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                choice[a] = c
    if dp[amount] == INF:
        return -1, []
    used, a = [], amount
    while a > 0:
        used.append(choice[a])
        a -= choice[a]
    return dp[amount], used

print(coin_change([1, 2, 5], 11))  # (3, [1, 5, 5])
print(coin_change([2], 3))         # (-1, [])
print(coin_change([1, 3, 4], 6))   # (2, [3, 3])
print(coin_change([1], 0))         # (0, [])

The [1, 3, 4] case is why this is DP and not greedy. Taking the largest coin first gives 4 + 1 + 1, three coins; the DP finds 3 + 3. Greedy is correct for some coin systems (such as 1, 5, 10, 25), but proving that for a given system is harder than just running the DP. When a greedy choice can be proven optimal, it is simpler and faster; see Greedy Algorithms for how those proofs work.

Counting the number of ways to make an amount uses the same table shape but a different combination rule, and whether the loop over coins is outside or inside the loop over amounts decides whether you count combinations or ordered sequences. That subtlety is covered in DP Patterns.

Counting problems and overflow

Counting DPs grow exponentially. The number of ways to climb 100 stairs already exceeds 2^63, the limit of a signed 64-bit integer. Python integers never overflow, so a Python solution gives the exact (huge) number; the same code in C++ or Java silently wraps around. That is why counting problems ask for the answer modulo 10^9 + 7. Apply the modulo at every addition, not just at the end, and in C++ use long long for anything that multiplies two values below the modulus:

MOD = 10**9 + 7

def count_ways(n):
    a, b = 1, 1               # ways to reach stair 0 and stair 1
    for _ in range(n - 1):
        a, b = b, (a + b) % MOD
    return b

print(count_ways(5), count_ways(1000))  # 8 107579939

Even in Python, applying the modulo as you go matters: without it the numbers grow to hundreds of digits, and each addition gets slower.

A Procedure for New DP Problems

Brute force first. Write the recursive solution that tries every choice. It defines what the subproblems are.
Find the arguments that change. The parameters of the recursive function that vary between calls are your state. If one of them is a list or a set of used items, the state space may be too large.
Write the one-sentence definition of the state and the recurrence that follows from it.
Count states × transitions and check it against the constraints.
Base cases from the definition, not from small examples worked out by hand.
Memoize, test against the brute force on small random inputs, then convert to bottom-up if depth or memory is a concern.

Step 6 is the one people skip. A brute force and a DP that agree on a few hundred random small inputs catch nearly every off-by-one in the table and the base case before a judge does.