Memoization vs Tabulation — When to Choose Which for DP

I remember the first time I encountered a dynamic programming problem. I had solved it recursively, but it was too slow. Someone told me to add memoization. I added an empty object, stored results in it, and the solution ran instantly. I felt like a genius. Then I solved the same problem with tabulation, and it ran even faster. That is when I realized both approaches work, but they suit different situations.

Memoization and tabulation are the two strategies for implementing dynamic programming. Both avoid recomputing subproblems, but they do it from opposite directions. Memoization starts at the goal and works backward recursively. Tabulation starts at the base cases and works forward iteratively. Understanding the difference helps you pick the right one without overthinking.

Memoization (Top-Down)

Memoization starts with the original problem and breaks it down recursively. Before computing a subproblem, it checks whether the result is already cached. If it is, return it. If not, compute it, store it, then return it. This is the closest to how humans naturally think about problems: start at the goal and work backward.

function fib(n, memo = {}) {
  if (n in memo) return memo[n]
  if (n <= 1) return n
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  return memo[n]
}

The diagram below shows what happens when you compute fib(5) with memoization. The repeated subtrees like fib(3) are computed once and retrieved from the cache on subsequent calls. The green dashed arrows show cache hits where the function returned immediately without recomputing.

Without memoization, fib(5) would make 15 function calls. With memoization, it makes only 9. The savings grow exponentially with larger inputs. For fib(10), memoization saves over 100 redundant calls.

The advantage of memoization is that it only computes the states actually needed. If the problem has a large state space but most states are not reachable, memoization wastes no time on them. The code also maps directly to the recursive solution, making it easy to derive from the brute force version.

The disadvantage is recursion depth. For problems with deep state spaces, you might hit the call stack limit. JavaScript’s default limit is around 10,000 calls, which is enough for most DP problems but not all. Memoization also uses more memory per cache entry because it stores the call stack alongside the cached values.

Tabulation (Bottom-Up)

Tabulation starts from the smallest subproblem and builds upward. You allocate a table, fill in the base cases, and iteratively compute each subsequent cell using the values already computed. There is no recursion, no call stack, no cache lookup overhead.

function fib(n) {
  if (n <= 1) return n
  const dp = [0, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

Tabulation is faster than memoization in most cases because it uses simple array accesses instead of function calls and hash map lookups. It also avoids stack overflow entirely. And it is often possible to optimize the space: for Fibonacci, you only need the last two values, so you can replace the entire array with two variables.

The disadvantage is that tabulation computes every state from 0 to n, even if some states are unnecessary. For problems with a sparse state space — like a grid with obstacles where most cells are blocked — tabulation wastes time filling in unreachable cells that memoization would skip.

When you put them side by side, the differences become clear. Here is how the two approaches compare across the dimensions that matter most in practice.

The diagram below puts the two approaches side by side. On the left, memoization starts from the top and breaks the problem down recursively, reusing cached results. On the right, tabulation starts from the bottom and builds up the solution iteratively, filling a table from left to right.

The pattern you should notice is that memoization trades recursion overhead for flexibility, while tabulation trades upfront computation for speed. Neither is universally better. The right choice depends on the shape of your problem and the constraints you are working under.

Real-World Example: Grid Traveler

Consider a problem where you need to count the number of ways to travel from the top-left corner to the bottom-right corner of a grid. You can only move down or right. How many distinct paths exist?

The recursive solution has a natural memoization pattern. For a 1x1 grid, there is exactly one way: you are already at the destination. For any larger grid, the number of ways equals the number of ways for the cell above plus the number of ways for the cell to the left. This recurrence is identical to the structure we saw with Fibonacci, but in two dimensions instead of one.

• Base case: If the grid is 1x1, there is exactly one way. If either dimension is zero, there are zero ways because the grid is invalid.
• Recursive case: ways(m, n) = ways(m-1, n) + ways(m, n-1). You either came from above or from the left.
• Cache key: Use m + "," + n as the key so that results for (2,3) and (3,2) are shared — they are mirror images of each other.

The visual below shows a 3x3 grid with the number of distinct paths to each cell. Starting from the top-left corner marked S, each cell accumulates paths from the cell above and the cell to the left. The bottom-right corner marked E shows 6 total paths.

With memoization, the solution runs in O(m × n) time and only computes states that are actually reachable from the recursive calls. With tabulation, you fill a 2D table row by row, computing each cell from the cell above and the cell to the left. Both approaches compute the same number of cells for a clean grid, but the difference becomes dramatic when obstacles are introduced.

If the grid has blocked cells that cannot be traversed, memoization skips them entirely because the recursive function never calls itself on a blocked cell. Tabulation must still iterate over every cell in the grid, check whether it is blocked, and skip it if necessary. For a grid where 50 percent of cells are blocked, memoization computes roughly half the states that tabulation does. This is the sparse state scenario where memoization clearly wins.

On the other hand, if the grid has no obstacles and you need to compute the number of paths for every cell anyway, tabulation is faster because it uses simple array accesses instead of recursive function calls. Tabulation also makes it trivial to optimize space: instead of storing the full 2D table, you can keep only the previous row and update it in place, reducing memory from O(m × n) to O(n).

Implementation Across Languages

Both memoization and tabulation translate easily into any language that supports recursion and arrays. The structure stays the same regardless of syntax — only the caching mechanism changes.

In Python, memoization is commonly done with a decorator. The @lru_cache decorator from functools automatically caches return values based on function arguments. Tabulation uses a simple list that you fill iteratively.

# Python memoization
from functools import lru_cache

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

# Python tabulation
def fib(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

In Java, memoization typically uses a HashMap with the function arguments as the key. Tabulation uses a plain array since the state space is usually a sequential integer range.

// Java memoization
import java.util.*;

Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long result = fib(n-1) + fib(n-2);
    memo.put(n, result);
    return result;
}

// Java tabulation
long fib(int n) {
    long[] dp = new long[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

In Rust, memoization can use a HashMap or a Vec of Option. The borrow checker ensures that cached values are not accidentally mutated. Tabulation uses a Vec that grows with the input size.

// Rust memoization
use std::collections::HashMap;

fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if let Some(&val) = memo.get(&n) { return val; }
    let val = if n <= 1 { n } else { fib(n-1, memo) + fib(n-2, memo) };
    memo.insert(n, val);
    val
}

// Rust tabulation
fn fib(n: usize) -> u64 {
    let mut dp = vec![0u64; n+1];
    if n >= 1 { dp[1] = 1; }
    for i in 2..=n {
        dp[i] = dp[i-1] + dp[i-2];
    }
    dp[n]
}

The pattern across all three languages is the same. Memoization requires a cache data structure and a recursive function. Tabulation requires an array and a loop. The choice between them depends more on the problem structure than on the language you are using.

Which One to Pick?

Here is the rule I use in practice.

• Start with memoization if the problem has a natural recursive formulation. It is easier to write and debug, and it avoids computing unnecessary states. Once the memoized solution passes the tests, measure whether performance is acceptable. If it is, ship it.
• Switch to tabulation if the memoized solution hits stack depth limits or if memory usage is too high. Tabulation is faster, uses less memory, and has no recursion risk.
• Start with tabulation if you already know every state from 0 to n will be computed. Problems like Fibonacci, grid traveler without obstacles, and longest common subsequence all have dense state spaces where tabulation is the natural fit.

Both approaches are valid. The best one is the one that matches how you think about the problem and that you can implement without introducing bugs. Over time, both will become natural, and you will reach for the appropriate one without conscious thought.