All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Memoization vs Tabulation — Deep Comparison

Memoization vs Tabulation — Deep Comparison

0/12 in this phase0/57 across the roadmap

📖 Concept

Both solve DP problems by caching results, but their approaches, tradeoffs, and use cases differ significantly.

Memoization (Top-Down):

  • Start from the main problem, recurse into sub-problems
  • Cache results in a hash map or array
  • Only computes sub-problems that are actually needed (lazy)
  • Uses the call stack (recursion)
  • Easier to write — just add caching to recursive solution

Tabulation (Bottom-Up):

  • Start from the smallest sub-problems, build up to the answer
  • Fill a table iteratively
  • Computes ALL sub-problems in order (eager)
  • No recursion — iterative loops
  • Can be space-optimized (rolling array)

Comparison:

Aspect Memoization Tabulation
Approach Top-down Bottom-up
Recursion Yes (call stack) No (iterative)
Lazy/Eager Lazy (only needed states) Eager (all states)
Space O(n) + call stack O(n) optimizable to O(1)
Stack overflow Possible for deep recursion Never
Ease Easier to derive Harder to get iteration order

When to use which:

  • Memoization: When not all states are needed, when recursion is natural, when you want quick implementation
  • Tabulation: When you need all states, want to avoid stack overflow, need space optimization, or want best performance

🏠 Real-world analogy: Memoization is like a student who only studies what's on the exam (lazy). Tabulation is like a student who studies the entire textbook systematically (eager). Both get the same grade, but the lazy student might save time if the exam is narrow.

💻 Code Example

codeTap to expand ⛶
1// FIBONACCI — Side by side comparison
2

3// MEMOIZATION (Top-Down)
4function fibMemo(n: number, cache: Map<number, number> = new Map()): number {
5  if (n <= 1) return n;
6  if (cache.has(n)) return cache.get(n)!;
7  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
8  cache.set(n, result);
9  return result;
10}
11

12// TABULATION (Bottom-Up)
13function fibTab(n: number): number {
14  if (n <= 1) return n;
15  const dp = [0, 1];
16  for (let i = 2; i <= n; i++) {
17    dp[i] = dp[i - 1] + dp[i - 2];
18  }
19  return dp[n];
20}
21

22// TABULATION with SPACE OPTIMIZATION
23function fibOptimal(n: number): number {
24  if (n <= 1) return n;
25  let a = 0, b = 1;
26  for (let i = 2; i <= n; i++) {
27    [a, b] = [b, a + b];
28  }
29  return b;
30}
31

32// LCS — Both approaches
33// Memoization
34function lcsMemo(s1: string, s2: string): number {
35  const cache = new Map<string, number>();
36  function dp(i: number, j: number): number {
37    if (i === 0 || j === 0) return 0;
38    const key = `${i},${j}`;
39    if (cache.has(key)) return cache.get(key)!;
40    let result: number;
41    if (s1[i-1] === s2[j-1]) result = dp(i-1, j-1) + 1;
42    else result = Math.max(dp(i-1, j), dp(i, j-1));
43    cache.set(key, result);
44    return result;
45  }
46  return dp(s1.length, s2.length);
47}
48

49// Tabulation
50function lcsTab(s1: string, s2: string): number {
51  const m = s1.length, n = s2.length;
52  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
53  for (let i = 1; i <= m; i++) {
54    for (let j = 1; j <= n; j++) {
55      dp[i][j] = s1[i-1] === s2[j-1]
56        ? dp[i-1][j-1] + 1
57        : Math.max(dp[i-1][j], dp[i][j-1]);
58    }
59  }
60  return dp[m][n];
61}
62

63// GENERIC MEMOIZE DECORATOR
64function memoize<T extends (...args: any[]) => any>(fn: T): T {
65  const cache = new Map<string, ReturnType<T>>();
66  return ((...args: Parameters<T>): ReturnType<T> => {
67    const key = JSON.stringify(args);
68    if (cache.has(key)) return cache.get(key)!;
69    const result = fn(...args);
70    cache.set(key, result);
71    return result;
72  }) as T;
73}

🏋️ Practice Exercise

Practice Problems:

  1. Solve climbing stairs with both memoization and tabulation
  2. Solve coin change with both approaches — compare
  3. Convert a tabulation solution to memoization (and vice versa)
  4. Implement a generic memoize decorator in TypeScript
  5. Solve unique paths with tabulation and optimize space to O(n)
  6. When would memoization be MORE efficient than tabulation?
  7. Write a problem where memoization causes stack overflow — convert to tabulation
  8. Implement LCS with space-optimized tabulation (O(n) space)
  9. Compare runtime of memo vs tab for fibonacci(40)
  10. Solve house robber with both approaches

⚠️ Common Mistakes

  • Using string keys for memoization cache — slow! Use tuple/array or Map with computed keys

  • Not recognizing that memoization can stack overflow for deep recursion — switch to tabulation

  • Assuming tabulation always computes unnecessary states — sometimes the iteration order naturally skips them

  • Forgetting that tabulation enables space optimization (rolling array) but memoization doesn't

  • Using memoization in production for non-recursive scenarios — tabulation is usually more efficient

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Memoization vs Tabulation — Deep Comparison

← PreviousDP — Advanced (Knapsack, Interval, State Machines)Next →Advanced Recursion (Tree Recursion, Tail Call Optimization)