Flipping the Direction
Memoization is Top-Down: start at the problem you want to solve (e.g., fib(10)), recurse down to smaller sub-problems, and cache results on the way back up.
Tabulation is Bottom-Up: start at the smallest sub-problems you already know the answer to (the base cases), and iteratively build up to the answer you want. No recursion at all — just a loop and an array.
Fibonacci via Tabulation
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1) # dp[i] will store fib(i)
dp[0] = 0 # Base case
dp[1] = 1 # Base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # Build from known values
return dp[n]
For fib(6), the table fills like this:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Value | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Memoization vs. Tabulation: When to Use Which
| Memoization (Top-Down) | Tabulation (Bottom-Up) | |
|---|---|---|
| Approach | Recursive + cache | Iterative + array |
| Stack Overflow risk | Yes, for deep recursion | No |
| Solves only needed sub-problems | Yes — lazy evaluation | No — fills entire table |
| Easier to reason about | Often yes | Sometimes harder |
| Performance | Slightly slower (function call overhead) | Slightly faster (cache-friendly) |
Rule of thumb: Start with Memoization (it's easier to derive from the recursive solution). Switch to Tabulation if you hit recursion depth limits or need maximum performance.
Space Optimization
Many DP problems only need the last one or two values, not the entire table. Fibonacci only needs dp[i-1] and dp[i-2]:
def fib(n):
if n <= 1: return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
This reduces space from O(N) to O(1) — a common interview optimization question.