Memoization vs Tabulation — Two Faces of DP

Memoization Top-Down

Start from the answer and recurse down to base cases. Cache results so each subproblem is solved only once.

Write the recursive solution first, then add a cache
Only solves subproblems that are actually needed
Uses recursion stack (risk of stack overflow for large N)
Easier to think about: matches the recurrence directly
Function call overhead per subproblem

Tabulation Bottom-Up

Start from base cases and build up to the answer iteratively. Fill a table in a defined order.

No recursion, just loops. No stack overflow risk
Solves ALL subproblems (even unused ones)
Often allows space optimization (keep only last row/few vars)
Faster in practice: no function call overhead
Need to figure out the correct fill order

Aspect	Memoization (Top-Down)	Tabulation (Bottom-Up)
Direction	Answer → Base cases	Base cases → Answer
Implementation	Recursion + cache	Loops + array
Subproblems solved	Only needed ones	All of them
Stack usage	O(depth) recursion stack	No recursion stack
Space optimization	Harder (need full cache)	Easy (rolling array)
Speed (practical)	Slower (function calls)	Faster (cache-friendly)
Ease of coding	Easier (just add memo)	Needs fill-order thinking
When to prefer	Sparse subproblem space, trees, graphs	Dense subproblem space, optimization needed

C++ — Fibonacci: Memoization (Top-Down)

unordered_map<int,int> memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n]; // cached!
    return memo[n] = fib(n-1) + fib(n-2);
}

C++ — Fibonacci: Tabulation (Bottom-Up)

int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(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];
}

// Space optimized O(1):
int fibOpt(int n) {
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b; a = b; b = c;
    }
    return n == 0 ? a : b;
}

🎯 Rule of Thumb

Start with memoization when thinking through the problem (it maps directly to the recurrence). Convert to tabulation when you need space optimization or the recursion depth is too large. In competitive programming, memoization is faster to code; in production, tabulation is faster to run.

📝 Notes

▼