Learn Tabulation vs Memoization — Free DSA Tutorial

Memoization

Memoization solves a problem top-down: it starts from the actual question you want answered and recursively breaks it into smaller pieces, caching each result the first time it's computed so later calls with the same arguments return instantly.

Example: Memoization

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> cache;
int fib(int n) {
	if (n <= 1) return n;
	if (cache.count(n)) return cache[n];
	return cache[n] = fib(n-1) + fib(n-2);
}
int main() { cout << "Top-down from fib(10): " << fib(10); return 0; }

import java.util.*;
public class Main {
	static Map<Integer,Integer> cache = new HashMap<>();
	static int fib(int n) {
		if (n <= 1) return n;
		if (cache.containsKey(n)) return cache.get(n);
		int r = fib(n-1) + fib(n-2);
		cache.put(n, r);
		return r;
	}
	public static void main(String[] args) { System.out.println("Top-down from fib(10): " + fib(10)); }
}

cache = {}
def fib(n):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]
print("Top-down from fib(10):", fib(10))

#include <stdio.h>
int cache[11]={0}, computed[11]={0};
int fib(int n) {
	if (n <= 1) return n;
	if (computed[n]) return cache[n];
	computed[n] = 1;
	return cache[n] = fib(n-1) + fib(n-2);
}
int main() { printf("Top-down from fib(10): %d", fib(10)); return 0; }

Tabulation

Tabulation solves the same kind of problem bottom-up: it starts from the smallest base cases, fills in a table in order, and builds up to the final answer without ever making a recursive call.

Example: Tabulation

#include <iostream>
using namespace std;
int main() {
	int dp[11]; dp[0]=0; dp[1]=1;
	for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
	cout << "Bottom-up table filled in order, dp[10] = " << dp[10];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dp = new int[11]; dp[0]=0; dp[1]=1;
		for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
		System.out.println("Bottom-up table filled in order, dp[10] = " + dp[10]);
	}
}

dp = [0]*11
dp[1] = 1
for i in range(2, 11):
    dp[i] = dp[i-1] + dp[i-2]
print("Bottom-up table filled in order, dp[10] =", dp[10])

#include <stdio.h>
int main() {
	int dp[11]; dp[0]=0; dp[1]=1;
	for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
	printf("Bottom-up table filled in order, dp[10] = %d", dp[10]);
	return 0;
}

Comparison

Both avoid the wasted, repeated computation of naive recursion, but they walk the dependency graph in opposite directions — memoization only computes states actually needed by the recursion, while tabulation computes every state in its table whether or not the final answer strictly requires it.

Example: Comparison

#include <iostream>
using namespace std;
int main() {
	cout << "Memoization computes only states the recursion actually needs; tabulation fills every state";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Memoization computes only states the recursion actually needs; tabulation fills every state");
	}
}

print("Memoization computes only states the recursion actually needs; tabulation fills every state")

#include <stdio.h>
int main() {
	printf("Memoization computes only states the recursion actually needs; tabulation fills every state");
	return 0;
}

When to Use

Memoization tends to feel more natural when you already have a working recursive solution and just want to speed it up; tabulation tends to be simpler to reason about, easier to space-optimize, and avoids the risk of recursion-depth stack overflows on large inputs.

Example: When to Use

#include <iostream>
using namespace std;
int main() {
	cout << "Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.");
	}
}

print("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.")

#include <stdio.h>
int main() {
	printf("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.");
	return 0;
}

Practice

There's no universally better choice — pick memoization when the recursive structure is clearer to write first, and pick tabulation when you want iterative code or need to control memory usage precisely.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "No universal winner -- pick based on which structure (recursive vs iterative) fits the problem";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem");
	}
}

print("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem")

#include <stdio.h>
int main() {
	printf("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem");
	return 0;
}

Tabulation vs Memoization

Memoization

Tabulation

Comparison

When to Use

Practice

Chapter Quiz — Complete all 12 topics to unlock

Login to run this code