Memoization vs Tabulation

There are two ways to write any DP solution. They produce the same answers and have the same big-O time complexity. They differ in how natural the code feels, how much memory they use, and how easy they are to optimize further.

If you’re stuck, start with memoization. Once it works, consider converting to tabulation for speed or to unlock space optimization. Don’t convert before it works — it’s a recipe for double bugs.

The same problem, three ways

Let’s use the same problem — climbing stairs — and write it as plain recursion, top-down DP, and bottom-up DP, side by side.

Style 1 — pure recursion (the brute force)

int climb(int n) {
    if (n <= 1) return 1;
    return climb(n - 1) + climb(n - 2);
}

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

int climb(int n) {
    if (n <= 1) return 1;
    return climb(n - 1) + climb(n - 2);
}

Correct. Time: O(2^n). Space: O(n) recursion depth. Times out on the LeetCode judge around n = 35.

Style 2 — memoization (top-down DP)

Add a cache. Check the cache before recursing; fill the cache before returning.

int climb(int n, vector<int>& memo) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
    return memo[n];
}
int climbStairs(int n) {
    vector<int> memo(n + 1, -1);
    return climb(n, memo);
}

from functools import lru_cache
 
def climb_stairs(n):
    @lru_cache(maxsize=None)
    def climb(k):
        if k <= 1: return 1
        return climb(k - 1) + climb(k - 2)
    return climb(n)

public int climbStairs(int n) {
    Integer[] memo = new Integer[n + 1];
    return climb(n, memo);
}
int climb(int n, Integer[] memo) {
    if (n <= 1) return 1;
    if (memo[n] != null) return memo[n];
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
    return memo[n];
}

Time: O(n). Space: O(n) for the cache + O(n) recursion stack.

Notice how the body of the function is identical to the brute force — only the cache check and write are new. This is the memoization template: take any recursion, sandwich the body between a cache hit-check and a cache write-back. Done.

Style 3 — tabulation (bottom-up DP)

Replace recursion with a loop that fills the table in order.

int climbStairs(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

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

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Time: O(n). Space: O(n). No recursion, no stack.

And because each cell only depends on the previous two, we can collapse the entire table to two variables:

int climbStairs(int n) {
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

def climb_stairs(n):
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

public int climbStairs(int n) {
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Time: O(n). Space: O(1). This is the space-optimized bottom-up form — and it’s why tabulation is worth converting to for problems with very tight rolling dependencies.

How to convert memoization to tabulation

The mechanical recipe:

Once you’ve done this conversion three or four times, you can do it in your head while reading the problem.

When to prefer each style

Prefer memoization when

• The state space is large but sparse. If most subproblems are never visited, tabulation wastes time filling the irrelevant cells. Memoization only computes what it needs.
• The transitions are complex. Multi-way recursion (try every split, every subset, every partition) is much easier to express as code that recurses than as a multi-loop table fill.
• You’re still figuring the problem out. Get the recursion right, slap a cache on, ship it. Optimize later if needed.

Prefer tabulation when

• You want to space-optimize. Tabulation lets you keep only the rows you still need (one or two at a time), often dropping O(n × m) memory down to O(m) or O(1). Memoization can’t do this — the cache has to hold every visited cell.
• You’re running into stack overflow. Deep recursion (state depth > ~10,000 in most languages) blows the stack. Tabulation has no stack.
• You want the absolute fastest constant factor. Tight inner loops with no function-call overhead matter on heavily-judged problems and competitive-programming benchmarks.

A side-by-side cheat sheet

For the same DP problem, here’s how the two styles compare on every axis:

A subtle gotcha: the base case in memo arrays

When you use -1 (or any sentinel value) to mean “not yet computed,” the sentinel must be a value the function can never legitimately return. If your DP computes counts that can be -1 (some Manhattan-distance puzzle, or a problem with “no solution → -1” outputs), pick a different sentinel — or use a parallel boolean computed[i] array, or use language-native nullable types (Integer in Java, Optional<int> in C++17, None in Python).

This is the kind of bug that doesn’t crash — it just silently returns wrong answers. Watch for it.

Quick check

Next: the classic patterns — seven shapes that show up in nearly every DP interview problem.