Memoization vs Tabulation

So you wrote a clean recursive solution. It works fine on small inputs. Then you give it a bigger number and it just hangs there forever. The reason is that your recursion keeps solving the same small piece again and again. Dynamic programming fixes this. It solves each small piece once and then remembers the answer. There are two ways to do that remembering. One is memoization and the other is tabulation. Let us learn both.

📚 What Are These Two Things?

Both memoization and tabulation are styles of dynamic programming. Dynamic programming means breaking a big problem into smaller repeating pieces. You store each piece’s answer so you never compute it twice.

The real difference is the direction you go.

• Memoization is top-down. You write the natural recursion, the one you would write anyway. Then you add a cache. Before you compute an answer, you check the cache. If it is there, you return it right away. If not, you compute it once and save it.
• Tabulation is bottom-up. You skip recursion completely. You start from the smallest pieces and fill a table from the bottom. Then you build up to the final answer step by step.

So it is the same idea seen from two directions. Memoization starts at the top problem and works down to the base. Tabulation starts at the base and works up to the top.

🍳 A Quick Analogy

Think about a cook learning recipes.

Memoization is like a cook who tries to make a big dish, realizes they need a sauce, makes the sauce, and writes it on a card so they never make that sauce from scratch again. They start from the final dish and work backward to whatever they need.

Tabulation is like a cook who first preps every basic ingredient and sauce in order, lines them up on the counter, and only then assembles the final dish. They start from the basics and build up.

Both cooks avoid repeating work. They just organize it differently.

🎯 The Shared Example: Fibonacci

We will use Fibonacci for both approaches. Fibonacci is a sequence where each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, and so on.

The plain recursion looks like fib(n) = fib(n-1) + fib(n-2). The trouble is that plain recursion recomputes the same values over and over. To get fib(5) it computes fib(3) twice and fib(2) three times. It gets much worse as n grows.

Here is how the calls explode for a small n. Notice how fib(2) shows up more than once.

Both memoization and tabulation kill this repeated work. Each fib value gets computed exactly once.

🔼 Approach 1: Memoization (Top-Down)

The idea here is simple. Keep the recursion you already know. Then add a cache that maps n to its answer. This style is called top-down because you start at the big problem and recurse down.

Steps to do memoization:

1. Make a cache (an array or a map) and mark every slot as empty.
2. Write the recursive function as normal, with the base cases first.
3. At the start of the function, check the cache. If the answer for n is already there, return it right away.
4. Otherwise compute the answer with the usual recursion.
5. Save that answer in the cache before you return it.

Here is Fibonacci with memoization in all five languages.

#include <stdio.h>

long long cache[100]; // stores answers; -1 means empty

// top-down fibonacci with a cache
long long fib(int n) {
    if (n < 2) return n;            // base cases: fib(0)=0, fib(1)=1
    if (cache[n] != -1)             // already computed?
        return cache[n];            // return the saved answer
    cache[n] = fib(n - 1) + fib(n - 2); // compute once, then save
    return cache[n];
}

int main(void) {
    for (int i = 0; i < 100; i++) cache[i] = -1; // mark all empty
    printf("fib(10) = %lld\n", fib(10));
    return 0;
}

fib(10) = 55

#include <iostream>
#include <vector>
using namespace std;

vector<long long> cache(100, -1); // -1 means empty

// top-down fibonacci with a cache
long long fib(int n) {
    if (n < 2) return n;          // base cases
    if (cache[n] != -1)           // already computed?
        return cache[n];          // return the saved answer
    cache[n] = fib(n - 1) + fib(n - 2); // compute once, then save
    return cache[n];
}

int main() {
    cout << "fib(10) = " << fib(10) << endl;
    return 0;
}

fib(10) = 55

import java.util.Arrays;

public class FibMemo {
    static long[] cache = new long[100];

    // top-down fibonacci with a cache
    static long fib(int n) {
        if (n < 2) return n;        // base cases
        if (cache[n] != -1)         // already computed?
            return cache[n];        // return the saved answer
        cache[n] = fib(n - 1) + fib(n - 2); // compute once, then save
        return cache[n];
    }

    public static void main(String[] args) {
        Arrays.fill(cache, -1);     // mark all empty
        System.out.println("fib(10) = " + fib(10));
    }
}

fib(10) = 55

# top-down fibonacci with a cache
def fib(n, cache):
    if n < 2:                    # base cases: fib(0)=0, fib(1)=1
        return n
    if cache[n] != -1:           # already computed?
        return cache[n]          # return the saved answer
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)  # compute once, then save
    return cache[n]

memo = [-1] * 100                # -1 means empty
print("fib(10) =", fib(10, memo))

fib(10) = 55

// top-down fibonacci with a cache
function fib(n, cache) {
  if (n < 2) return n;            // base cases: fib(0)=0, fib(1)=1
  if (cache[n] !== -1)            // already computed?
    return cache[n];              // return the saved answer
  cache[n] = fib(n - 1, cache) + fib(n - 2, cache); // compute once, then save
  return cache[n];
}

const memo = new Array(100).fill(-1); // -1 means empty
console.log("fib(10) =", fib(10, memo));

fib(10) = 55

🔽 Approach 2: Tabulation (Bottom-Up)

Here we drop recursion. We make a table, fill the smallest answers first, then walk upward with a simple loop. This style is called bottom-up because you start at the smallest pieces and build toward the answer.

Steps to do tabulation:

1. Make a table (an array) of size n + 1.
2. Fill in the base cases by hand: table[0] = 0 and table[1] = 1.
3. Loop from the smallest unknown index up to n.
4. At each step set table[i] = table[i-1] + table[i-2], using values you already filled.
5. When the loop ends, table[n] holds the final answer.

Here is Fibonacci with tabulation in all five languages.

#include <stdio.h>

// bottom-up fibonacci using a table
long long fib(int n) {
    if (n < 2) return n;        // base cases
    long long table[100];
    table[0] = 0;               // smallest answers filled by hand
    table[1] = 1;
    for (int i = 2; i <= n; i++) // build upward
        table[i] = table[i - 1] + table[i - 2];
    return table[n];            // final answer sits at the top
}

int main(void) {
    printf("fib(10) = %lld\n", fib(10));
    return 0;
}

fib(10) = 55

#include <iostream>
#include <vector>
using namespace std;

// bottom-up fibonacci using a table
long long fib(int n) {
    if (n < 2) return n;        // base cases
    vector<long long> table(n + 1);
    table[0] = 0;               // smallest answers filled by hand
    table[1] = 1;
    for (int i = 2; i <= n; i++) // build upward
        table[i] = table[i - 1] + table[i - 2];
    return table[n];            // final answer sits at the top
}

int main() {
    cout << "fib(10) = " << fib(10) << endl;
    return 0;
}

fib(10) = 55

public class FibTab {
    // bottom-up fibonacci using a table
    static long fib(int n) {
        if (n < 2) return n;        // base cases
        long[] table = new long[n + 1];
        table[0] = 0;               // smallest answers filled by hand
        table[1] = 1;
        for (int i = 2; i <= n; i++) // build upward
            table[i] = table[i - 1] + table[i - 2];
        return table[n];            // final answer sits at the top
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
    }
}

fib(10) = 55

# bottom-up fibonacci using a table
def fib(n):
    if n < 2:                   # base cases
        return n
    table = [0] * (n + 1)
    table[0] = 0                # smallest answers filled by hand
    table[1] = 1
    for i in range(2, n + 1):   # build upward
        table[i] = table[i - 1] + table[i - 2]
    return table[n]             # final answer sits at the top

print("fib(10) =", fib(10))

fib(10) = 55

// bottom-up fibonacci using a table
function fib(n) {
  if (n < 2) return n;          // base cases
  const table = new Array(n + 1).fill(0);
  table[0] = 0;                 // smallest answers filled by hand
  table[1] = 1;
  for (let i = 2; i <= n; i++) { // build upward
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];              // final answer sits at the top
}

console.log("fib(10) =", fib(10));

fib(10) = 55

⚖️ Which One Should You Pick?

Both give you the same answer with the same O(n) time. The choice is about how you like to think and what the problem needs.

Here is a side-by-side look.

A simple rule of thumb. If you already have a working recursion and just want it fast, reach for memoization. If n can be huge and you fear a stack overflow, or you want the fastest loop, reach for tabulation.

⚠️ Common Mistakes

Watch out for these slip-ups when you write either approach.

• Forgetting to initialize the cache to an “empty” marker. If your empty marker is 0, but a real answer can also be 0, you will get confused results. Use -1 or a separate “filled” flag.
• Returning before checking the cache in memoization. Always check the cache first, then compute. Otherwise you lose the whole benefit.
• Wrong table size in tabulation. The table must be size n + 1 so that index n exists. An off-by-one here causes an out-of-bounds crash.
• Filling the table in the wrong order. In tabulation you must fill smaller indices before the ones that depend on them. Loop upward, not downward.
• Overflow on large n. Fibonacci grows fast. Use a 64-bit type like long long or long, or a big-integer type, when n gets large.

🧩 What You’ve Learned

• ✅ Dynamic programming solves each small subproblem once and stores the answer, so it never repeats work.
• ✅ Memoization is top-down: keep your natural recursion and add a cache that returns saved answers right away.
• ✅ Tabulation is bottom-up: skip recursion, fill a table from the smallest pieces, and build up to the final answer.
• ✅ Both run in O(n) time for Fibonacci, but tabulation avoids the call stack and is often a bit faster.
• ✅ Memoization is easiest when you already have a recursion; tabulation is safer for huge inputs and can sometimes drop space to O(1).

🚀 What’s Next?

• Introduction to Dynamic Programming
• Fibonacci with DP