Memoization vs Tabulation: Top-Down vs Bottom-Up Dynamic Programming

There are two ways to implement any dynamic programming solution. Memoization (top-down) writes the natural recursion and caches each result so it’s computed only once. Tabulation (bottom-up) fills a table iteratively from the base cases upward. Both compute the same states and have the same big-O time — this page shows the same DP both ways and explains when to pick each.

Memoization (top-down)

Start from the answer you want and recurse toward the base cases, storing every computed result in a cache (array or hash map). Before doing any work, check the cache; if the state is already solved, return it instantly.

#include <vector>
std::vector<long long> memo;
long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];      // cache hit
    return memo[n] = fib(n - 1) + fib(n - 2);
}
// caller: memo.assign(n + 1, -1); fib(n);

long[] memo;
long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];      // cache hit
    return memo[n] = fib(n - 1) + fib(n - 2);
}
// caller: memo = new long[n + 1]; Arrays.fill(memo, -1); fib(n);

function fib(n, memo = new Array(n + 1).fill(-1)) {
  if (n < 2) return n;
  if (memo[n] !== -1) return memo[n];       // cache hit
  return (memo[n] = fib(n - 1, memo) + fib(n - 2, memo));
}

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)          # cache handled by decorator

The recursion mirrors the math exactly, so memoization is usually the fastest to write and easiest to reason about. The cost is recursion overhead and the risk of a stack overflow for deep states.

Tabulation (bottom-up)

Solve the smallest subproblems first and build up. No recursion — just a loop filling a table in an order that guarantees every dependency is ready before you need it.

long long fib(int n) {
    if (n < 2) return n;
    std::vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;                    // base cases
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];      // transition
    return dp[n];
}

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

function fib(n) {
  if (n < 2) return n;
  const dp = new Array(n + 1);
  dp[0] = 0; dp[1] = 1;                      // base cases
  for (let i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];          // transition
  return dp[n];
}

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1                      # base cases
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]       # transition
    return dp[n]

How to choose

Aspect	Memoization (top-down)	Tabulation (bottom-up)
Code shape	recursion + cache	loops + table
Computes	only states you reach	all states in range
Overhead	function calls, stack	none
Stack risk	yes (deep recursion)	no
Easiest for	tricky/sparse state spaces	clear iteration order

For beginners: Write the recursion first to discover the recurrence, then add a cache (memoization). Once it works, you can often convert to tabulation mechanically for speed and to avoid deep recursion.

Space optimization

Tabulation opens the door to space optimization: if dp[i] depends only on the last couple of entries, you can drop the whole table and keep a few variables — reducing O(n) space to O(1). Fibonacci needs only the previous two values:

long long fib(int n) {
    if (n < 2) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

long fib(int n) {
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
    return b;
}

function fib(n) {
  if (n < 2) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) { const c = a + b; a = b; b = c; }
  return b;
}

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

Going deeper: Memoization can also be space-optimized in principle, but it’s awkward — you need all cached states alive during recursion. Bottom-up is the natural home for rolling-array tricks. You’ll see this pattern again in Fibonacci & Climbing Stairs and 0/1 Knapsack.

Both styles are correct; pick whichever makes the recurrence clearest, then optimize.