Memoization vs Tabulation

The Core Difference

Both memoization and tabulation are implementations of the same DP algorithm. They compute the same values using the same recurrence and produce identical answers. The difference is when and how each state is computed.

MEMOIZATION (top-down):           TABULATION (bottom-up):
  Start from the question.          Start from the answers.
  Recurse lazily toward base.       Fill eagerly from base up.
  Compute only needed states.       Compute ALL states in range.
  Cache results for reuse.          Table filled sequentially.

MENTAL MODEL:
  Memoization: "I need fib(10).     Tabulation: "I'll compute
    Let me check if I've done         fib(0), fib(1), ..., fib(10)
    this. No? Then I'll compute       in order. When I need fib(10),
    it and remember."                 it's already in the table."

BOTH ACHIEVE:
  O(unique sub-problems) time
  O(unique sub-problems) space (before space optimisation)

Head-to-Head Comparison

DIMENSION              MEMOIZATION          TABULATION
──────────────────────────────────────────────────────────────────
Execution direction    Top-down             Bottom-up
States computed        Only reachable        All in range
Code structure         Recursive             Iterative loops
Base cases             Inside function       Pre-loop initialisation
Cache structure        HashMap or array      Array (always)
Recursion overhead     Yes (per call)        None
Stack overflow risk    Yes (deep recursion)  None
Cache locality         Poor (HashMap)        Excellent (sequential)
Space optimisation     Hard                 Easy (rolling arrays)
Ease of first draft    Easier               Harder (fill order)
Performance (large n)  Slower in practice   Faster in practice
Handles sparse states  Yes (skips them)      No (fills all)
Typical use case       Complex DAGs,         Well-defined ranges,
                       interval DP,          1D/2D sequences,
                       sparse problems       dense sub-problems

Scenario 1: Dense Sub-Problems — Tabulation Wins

When most or all states in the table are reached, tabulation's sequential access dominates.

EXAMPLE: Fibonacci for large n

n = 1,000,000

MEMOIZATION:
  1,000,001 function calls
  Each call: push frame, check dict, hash key, pop frame
  Python dict lookup: ~50ns per call
  Total: ~50ms + recursion stack overflow risk

TABULATION:
  Single loop: 1,000,000 iterations
  Each iteration: dp[i] = dp[i-1] + dp[i-2] (2 adds, 2 reads)
  Array access: ~1ns per iteration (cache-hot)
  Total: ~1ms, no stack risk

RATIO: ~50× slower for memoization, same O(n) asymptotic complexity.

STANDARD DENSE DP PROBLEMS WHERE TABULATION IS PREFERRED:
  Fibonacci, Climbing Stairs, House Robber
  Unique Paths (m×n grid — all cells reached)
  Longest Common Subsequence (entire m×n table filled)
  Minimum Path Sum
  Edit Distance

Scenario 2: Sparse Sub-Problems — Memoization Wins

When only a fraction of all possible states are actually needed, memoization avoids wasteful computation.

EXAMPLE: Top-Down DAG DP with sparse reachable states

Problem: You have items indexed 1..1000, weights 1..1000.
For knapsack, we compute dp[i][w] for i in [1..1000], w in [1..1000].
That's 1,000,000 states total.

BUT: if the items have large weights (minimum weight = 900),
only ~11 weights per item are valid (900, 901, ..., 1000).
Reachable states: 1000 × 11 = 11,000 out of 1,000,000.

TABULATION:  Fills all 1,000,000 cells. 989,000 are wasted work.
MEMOIZATION: Fills only 11,000 reachable cells. 89× less work.

OTHER SPARSE EXAMPLES:
  Interval DP with skip conditions
  Word break where only some prefix lengths are valid
  Game theory DP where only certain game states are reachable
  3D or higher-dimensional DP where most states are unreachable

Scenario 3: Deep Recursion — Tabulation Avoids Stack Overflow

PROBLEM: Memoized fib(100000) in Python

Default recursion limit: 1000 frames.
fib(100000) requires 100000 nested calls → CRASH.

sys.setrecursionlimit(200000) is a workaround but:
  - Wastes memory for 200000 stack frames
  - Python stack frame: ~300 bytes → 60MB just for stack
  - C stack has a hard OS limit (typically 8MB on Linux)
  - Still crashes for n > ~30000 with default 8MB stack

TABULATION:
  for i in range(2, 100001):
      dp[i] = dp[i-1] + dp[i-2]
  No recursion. O(1) stack. Works for any n.

LANGUAGES MOST AFFECTED:
  Python:  Recursion limit 1000 (easily hit for n > 1000)
  Java:    Stack size configurable (-Xss), defaults ~512KB-1MB
  C++:     OS stack limit (~1-8MB), about 20000-100000 frames
  JavaScript: Typically 10000-15000 calls before stack overflow

RULE: If n > 10000, prefer tabulation to avoid stack issues.
  If n > 1000 in Python, prefer tabulation.

Side-by-Side Code: Same Problem, Both Approaches

Output:
House Robber:
  Memoized:   12
  Tabulated:  12
  Optimised:  12
LCS:
  Memoized:   3
  Tabulated:  3
Word Break (memo): true
Word Break (tab):  true

When Memoization Is Easier to Write

Some problems have complex state transitions that are easier to express recursively.

PROBLEMS WHERE MEMOIZATION SHINES STRUCTURALLY:

1. INTERVAL DP — "Burst Balloons", "Matrix Chain Multiplication"
   try_all_k: dp[i][j] = max over k in [i,j]: cost(i,k,j) + dp[i][k] + dp[k][j]

   Memoization: write the recursion naturally.
   Tabulation: must fill by interval length (non-obvious loop order).

2. WORD BREAK / STRING SEGMENTATION
   "Can s[start..] be segmented?"
   Memoization: dp(start) tries all splits naturally.
   Tabulation: dp[i] iterating backwards over j is less intuitive.

3. TREE/GRAPH DP — "House Robber III (binary tree)"
   Recursion IS the natural traversal.
   Memoization on tree node directly — tabulation would need to flatten the tree.

4. GAME THEORY DP — Minimax, Stone Game
   Recursive win/lose logic is clearest in recursive form.
   Tabulation requires carefully tracking whose turn it is.

PRACTICAL APPROACH:
  Step 1: Write the memoized solution (faster to implement).
  Step 2: If performance is insufficient, convert to tabulation.
  Step 3: If space is the bottleneck, apply rolling array to tabulation.

Choosing the Right Approach

USE MEMOIZATION WHEN:
  ✓ Problem structure is naturally recursive (trees, graphs, intervals)
  ✓ Sub-problem space is SPARSE — only a small fraction of states reachable
  ✓ You need to write correct code quickly (interview, prototyping)
  ✓ Fill order for tabulation is non-obvious (interval DP, game DP)
  ✓ States have non-integer or complex keys (use HashMap naturally)
  ✓ n is small (< 1000 in Python, < 10000 in Java/C++)

USE TABULATION WHEN:
  ✓ Sub-problem space is DENSE — most states in the range are needed
  ✓ n is large (> 10000 in any language, > 1000 in Python)
  ✓ Space optimisation (rolling arrays) is needed or desired
  ✓ You need predictable performance (no recursion overhead)
  ✓ The fill order is obvious (1D, standard 2D grid)
  ✓ Production code where recursion limit is a concern

EITHER WORKS (choose by comfort):
  ✓ Standard 1D DP (Fibonacci, Climbing Stairs, House Robber)
  ✓ Standard 2D DP (LCS, Edit Distance, Unique Paths)
  ✓ Knapsack variants

DECISION FLOWCHART:
  Is the recursive structure very clear?
    YES → Start with memoization
    NO  → Go directly to tabulation

  Are sub-problems sparse (most states unreachable)?
    YES → Keep memoization
    NO  → Consider tabulation

  Is n > 1000 in Python or > 100000 in Java/C++?
    YES → Use tabulation (avoid stack overflow)
    NO  → Either works

  Is space optimisation needed?
    YES → Use tabulation (rolling arrays much easier)
    NO  → Either works

Practical Conversion: When to Switch

REAL WORKFLOW:

1. PROTOTYPE with memoization
   - Write the recursion: natural, matches the problem statement
   - Add cache: two lines
   - Verify correctness on examples
   
2. PROFILE if needed
   - Is it too slow? → Convert to tabulation
   - Is stack overflowing? → Convert to tabulation
   - Is memory too high? → Add space optimisation to tabulation
   
3. OPTIMISE with tabulation
   - Convert recursive calls to table lookups
   - Remove cache check (loop order handles freshness)
   - Apply rolling array if space is critical

THE CONVERSION IS MECHANICAL:
  fib(n-1)        →  dp[i-1]
  fib(n-2)        →  dp[i-2]
  if base_case    →  explicit dp[0]=, dp[1]=
  memo[n] = val   →  dp[i] = val (in loop body)
  return memo[n]  →  return dp[n] (after loop)

EXAMPLE: House Robber memoized → tabulated

MEMOIZED:                         TABULATED:
  memo = {}                         dp = [0]*n
  def rob(i):                       dp[0] = nums[0]
    if i<0: return 0                dp[1] = max(nums[0],nums[1])
    if i==0: return nums[0]         for i in range(2,n):
    if i in memo: return memo[i]        dp[i] = max(dp[i-1],
    memo[i] = max(rob(i-1),                       dp[i-2]+nums[i])
                  rob(i-2)+nums[i])  return dp[n-1]
    return memo[i]
  return rob(n-1)

Performance Summary

CONSTANT FACTOR COMPARISON (same asymptotic complexity):

Operation          Memoization                   Tabulation
───────────────────────────────────────────────────────────────
Per-state cost     ~20-100 instructions          ~3-10 instructions
                   (function call + hash lookup  (array access + arithmetic)
                   + cache check + store)

Memory access      Random (HashMap, pointer      Sequential (array, row-major)
pattern            indirection)                  → cache-friendly

Stack memory       O(depth) frames               O(1) (loop counter only)

Total factor       ~10-50× slower for dense      Baseline fast
(empirical)        sub-problems

FOR CORRECTNESS:   Identical — same answer guaranteed
FOR INTERVIEWS:    Memoization is faster to write; tabulation may be faster to run
FOR PRODUCTION:    Tabulation preferred for performance-critical paths

Summary

Memoization and tabulation implement the same DP algorithm from opposite directions. They always produce identical answers. The choice is about implementation convenience and runtime efficiency.

Memoization (top-down):

• ›Write the recursion naturally, add two lines (cache check + store)
• ›Only computes reachable states (lazy)
• ›Easier to write for complex recursive structures (interval DP, tree DP)
• ›Risk: stack overflow for large n; slower due to function call overhead

Tabulation (bottom-up):

• ›Fill a table iteratively in dependency order
• ›Computes all states in range (eager)
• ›Faster in practice: sequential memory, no recursion overhead
• ›Easier to apply space optimisation (rolling arrays)

The decision:

The practical workflow: prototype with memoization → verify correctness → convert to tabulation if performance or stack depth demands it.

In the next topic you will explore 1D Dynamic Programming — solving problems where the state is a single index, including classic patterns like House Robber, Jump Game, Decode Ways, and Word Break.