Memoization vs Tabulation

Dynamic programming can be implemented in two equivalent styles: top-down with memoization (recursive + cache) or bottom-up with tabulation (iterative table fill). Both store subproblem answers—the difference is order of computation and coding style.

Overview

Both approaches solve the same DP recurrence. Memoization starts from the full problem and lazily fills a cache when subproblems are needed. Tabulation starts from base cases and builds the table forward until the final answer is known.

Top-down (memoization)          Bottom-up (tabulation)
─────────────────────          ─────────────────────
solve(n)                       dp[0], dp[1] = base cases
  └─ needs solve(n-1)            for i = 2 … n:
  └─ needs solve(n-2)                dp[i] = f(dp[i-1], dp[i-2])
  cache results on return          return dp[n]
return cached if seen

Top-Down: Memoization

Write the natural recursive solution, then store each state’s result in an array or hash map before returning. Unvisited states are never computed.

Bottom-Up: Tabulation

Fill a DP table iteratively from smallest subproblems upward. You must determine the correct loop order so dependencies are ready before they are used.

Side-by-Side Comparison

Fibonacci Example

Both versions compute the same sequence; compare structure and storage.

Memoization (top-down)

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Tabulation (bottom-up)

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Space-optimized tabulation (O(1) extra space)

def fib_tab_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Real-World Example Comparison

Tracing fib(5) side by side shows how memoization prunes repeated work while tabulation fills every cell in order.

Detailed Fibonacci with Call Stack Visualization

Memoization call flow:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1 (cached)
│   │   │   └── fib(0) → 0 (cached)
│   │   └── fib(1) → 1 (cached)
│   └── fib(2) → 1 (cached)
└── fib(3) → 2 (cached)

Total recursive calls: 9 (vs 15 without memoization)
States cached: {0, 1, 2, 3, 4, 5}

Tabulation fill order:

dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp[5] = dp[4] + dp[3] = 3 + 2 = 5

Total iterations: 5 (n − 1)
States computed: all from 0 to n

When to Use Each Approach

Use this decision framework once you have a clear recurrence. Both styles are valid—the choice depends on constraints, state shape, and whether you need a quick draft or a production-ready solution.

Decision Flowchart

Start here: Do you have a clear recurrence?

Practical Scenarios

Scenario 1: Quick interview solution

# Start with memoization for clarity
def solve_memo(state, memo):
    if base_case:
        return value
    if state in memo:
        return memo[state]
    result = recurrence(state)
    memo[state] = result
    return result

Scenario 2: Production code (large input)

# Use tabulation with space optimization
def solve_tab(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

Scenario 3: Complex state (multiple dimensions)

# Tabulation with careful iteration order
def solve_2d(m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + cost[i][j]
    return dp[m][n]

Space Optimization

Tabulation often allows rolling arrays: keep only the previous row or last two values when the recurrence depends on recent states only.

• 1D DP: Fibonacci, climbing stairs — O(n) table → O(1) with two variables
• 2D DP: Unique paths — O(m×n) table → O(n) with one row
• Memoization: Cache size equals distinct visited states; cannot always drop the stack

Common Interview Questions by Approach

Questions Where Memoization is Preferred

1. Word Break — only need to check specific positions
2. Word Break II — need to reconstruct paths; DFS + memo
3. Decode Ways — natural recursive structure
4. Coin Change — recursive formulation is intuitive
5. Regular Expression Matching — complex recurrence, sparse states

Questions Where Tabulation is Preferred

1. Unique Paths — simple grid iteration
2. Minimum Path Sum — 2D grid DP
3. Longest Common Subsequence — table visualization
4. Edit Distance — clear 2D table
5. Knapsack — weight iteration order
6. Maximum Subarray — Kadane's algorithm (O(1) space)

Questions Where Either Works Equally Well

1. Climbing Stairs — simple 1D DP
2. House Robber — linear DP
3. Fibonacci — classic example
4. Jump Game — greedy works best, but DP works too

Performance Metrics Comparison

Time Complexity Breakdown

Space Complexity Comparison

Real-World Performance Test (Fibonacci n = 40)

Advanced Techniques

1. Lazy Tabulation (Hybrid Approach)

Start with recursion but use iterative fill for performance-critical sections.

def hybrid_dp(n):
    # Use memoization for exploration
    # But use tabulation for known patterns
    def explore(state):
        if state in memo:
            return memo[state]
        if state < threshold:
            # Use precomputed tabulation
            return precomputed[state]
        result = recurrence(state)
        memo[state] = result
        return result

2. Memoization with LRU Cache (Python)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

3. Iterative with History (For Debugging)

def dp_with_history(n):
    dp = [0] * (n + 1)
    choices = [None] * (n + 1)  # Track decisions

    for i in range(1, n + 1):
        # Record which choice was made
        if take_option:
            dp[i] = best_value
            choices[i] = "took option"

    # Reconstruct solution
    path = reconstruct(choices)
    return dp[n], path

Common Pitfalls and How to Avoid Them

1. Infinite recursion in memoization — cyclic dependencies cause infinite loops. Solution: ensure the recurrence strictly reduces problem size.
2. Wrong fill order in tabulation — using dp[i+1] before it is computed. Solution: map dependencies and compute in topological order.
3. Forgetting base cases — missing base cases or wrong initialization. Solution: test with smallest inputs first.
4. Cache invalidation — not clearing memo between test cases. Solution: create a new memo for each call or use timestamps.
5. Memory blowup in 2D DP — O(m×n) table for large inputs. Solution: use rolling arrays or optimize to O(min(m, n)).
6. Premature optimization — trying to optimize space before correctness. Solution: first get a correct solution, then optimize.

Practice Problems with Solutions

Beginner Problems

1. Climbing Stairs (LeetCode 70)
   • Memoization: easy recursive + cache
   • Tabulation: O(n) array
   • Optimized: O(1) space with two variables
2. Min Cost Climbing Stairs (LeetCode 746)
   • Memoization: natural recursion
   • Tabulation: O(n) array
   • Optimized: O(1) space

Intermediate Problems

3. House Robber (LeetCode 198)
   • Memoization: simple state definition
   • Tabulation: O(n) array
   • Optimized: O(1) space
4. Decode Ways (LeetCode 91)
   • Memoization: intuitive recursion
   • Tabulation: O(n) array
   • Optimized: O(1) space
5. Unique Paths (LeetCode 62)
   • Memoization: 2D recursion
   • Tabulation: 2D table
   • Optimized: O(n) row compression

Advanced Problems

6. Coin Change (LeetCode 322)
   • Memoization: recursive with target state
   • Tabulation: O(amount) array
   • Both work equally well
7. Edit Distance (LeetCode 72)
   • Memoization: 2D recursion
   • Tabulation: 2D table
   • Optimized: O(n) space with rolling array

Interview Tips for Each Approach

Memoization Interview Tips

1. Start recursive — natural to explain
2. Add cache — mention memoization explicitly
3. Handle base cases first — always check termination
4. Explain overhead — mention recursion stack
5. Discuss trade-offs — time vs space
6. Be ready to convert — interviewers may ask for an iterative version

Tabulation Interview Tips

1. Draw the table — visualize on whiteboard
2. Explain fill order — show dependency graph
3. Start from base — explain initialization
4. Optimize space — mention rolling arrays if applicable
5. Trace example — walk through small input
6. Discuss alternatives — why tabulation over memoization?

Common Interview Follow-ups

• "Can you implement the iterative version?"
• "How would you optimize space?"
• "What's the time and space complexity?"
• "Can you identify the overlapping subproblems?"
• "How would you handle large inputs?"

Quick Reference Card

Memoization vs Tabulation Quick Reference

When to Use Which

Space Optimization Techniques

1. 1D DP → O(1) with variables
2. 2D DP → O(n) with rolling array
3. Multiple dimensions → keep only necessary rows
4. Sparse DP → use dictionary/hash map
5. Path reconstruction → store choices separately

Real-Life Applications

In production systems, the memoization vs tabulation choice mirrors how software computes on demand versus precomputes and stores results.