Introduction
Once a problem is confirmed to have overlapping subproblems and optimal substructure, there are two standard ways to implement the DP solution: memoization (top-down) and tabulation (bottom-up). Memoization keeps the natural recursive structure and adds a cache so each unique subproblem is computed only once. Tabulation instead builds an explicit table iteratively, starting from the smallest subproblems and working up to the final answer, avoiding recursion entirely. Both compute the same result and share the same asymptotic time complexity, but they differ in space usage, call overhead, and code style.
Cricket analogy: Memoization is like a scorer who only calculates a partnership's run-rate when a commentator actually asks about it, caching the answer, while tabulation is like pre-building the entire over-by-over run-rate table from ball one regardless of which overs get referenced.
Approach/Syntax
# Top-down (memoization): recursive with a cache
def climb_stairs_memo(n, cache=None):
if cache is None:
cache = {}
if n <= 2:
return n
if n in cache:
return cache[n]
cache[n] = climb_stairs_memo(n - 1, cache) + climb_stairs_memo(n - 2, cache)
return cache[n]
# Bottom-up (tabulation): iterative with an explicit table
def climb_stairs_tab(n):
if n <= 2:
return n
table = [0] * (n + 1)
table[1], table[2] = 1, 2
for i in range(3, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]Explanation
climb_stairs_memo starts from the original problem (n) and recurses down to base cases, filling the cache lazily — only subproblems actually needed for this input get solved. climb_stairs_tab starts from the base cases (n=1, n=2) and iterates forward, filling every table entry up to n in order, since each entry table[i] only depends on the two entries before it. Tabulation avoids Python's recursion-depth limit and function-call overhead, and it makes it easy to apply a further optimization — since table[i] only needs the last two values, the array can be replaced with two scalar variables, reducing space from O(n) to O(1).
Cricket analogy: A top-down projection to over 10 recurses down to over 1's base case, computing only the overs actually needed, while a bottom-up table starts at over 1 and 2 and iterates forward filling every over, later collapsing to two running totals since each over only needs the prior two.
Example
def climb_stairs_tab_optimized(n):
if n <= 2:
return n
prev2, prev1 = 1, 2 # table[1], table[2]
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
for n in [1, 2, 5, 10]:
memo_result = climb_stairs_memo(n)
tab_result = climb_stairs_tab(n)
opt_result = climb_stairs_tab_optimized(n)
print(f"n={n}: memo={memo_result}, tab={tab_result}, optimized={opt_result}")Output/Complexity
The traced loop prints matching results for all three implementations, for example 'n=10: memo=89, tab=89, optimized=89'. All three run in O(n) time. climb_stairs_memo uses O(n) space for the cache plus O(n) recursion-call stack depth; climb_stairs_tab uses O(n) space for the explicit table but no recursion stack; climb_stairs_tab_optimized reduces space to O(1) by keeping only the last two values, a rolling-array trick that only tabulation makes straightforward to spot. In general, prefer memoization when the recursive structure is easier to reason about or when only a subset of the state space is actually reachable; prefer tabulation when you need predictable performance, want to avoid recursion limits, or want to apply space optimizations.
Cricket analogy: Both a lazily-cached and a pre-tabulated run-rate calculator agree on the final figure, both running in O(n) overs, but the cached version carries recursion-stack overhead per over while the pre-tabulated one avoids it and can shrink to O(1) by tracking only the last two overs.
Key Takeaways
- Memoization is top-down: recursive code plus a cache keyed by subproblem parameters.
- Tabulation is bottom-up: an iterative loop that fills a table from base cases upward.
- Both have the same asymptotic time complexity for problems where all subproblems must be solved.
- Tabulation avoids recursion overhead and Python's recursion-depth limit, and enables O(1)-space rolling-array optimizations.
- Memoization can be faster in practice when only a fraction of the full state space is actually needed.
Practice what you learned
1. What is the key difference between memoization and tabulation?
2. Why might tabulation be preferred over memoization in Python specifically?
3. In climb_stairs_tab_optimized, why can the O(n) table be reduced to O(1) space?
4. When is memoization likely to outperform tabulation in practice?
Was this page helpful?
You May Also Like
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.
Recursion vs Iteration
Compare recursive and iterative solutions in terms of clarity, performance, memory usage, and when to prefer each.
Longest Common Subsequence
Master the LCS DP recurrence for finding the longest shared subsequence between two strings in O(mn) time.