Memoization and tabulation are the two ways to implement dynamic programming. Memoization is top-down: write the recursive solution, then cache results so each subproblem is computed once. Tabulation is bottom-up: fill a table iteratively, from the smallest subproblems up to the answer. Both give the same time complexity for the same recurrence; they differ in how you write them and in a few practical limits such as recursion depth.
When dynamic programming applies
A problem is a DP candidate when it has two properties:
- Optimal substructure. The answer for the whole problem can be built from answers to smaller versions of it.
- Overlapping subproblems. The same smaller versions are needed again and again.
The second property is what makes DP faster than plain recursion. Without overlap (merge sort, for example) there is nothing to cache.
The workflow that works on most problems is the same every time:
- Define the state: what do the arguments of the function mean? (“The fewest coins needed to make
rem.”) - Write the recurrence that relates a state to smaller states.
- Identify the base cases.
- Decide the order in which states depend on each other (this tells you the loop order for tabulation).
- Read the answer from the state that represents the full problem.
Why the naive recursion is too slow
Fibonacci shows the problem clearly. Here is the plain recursive version with a call counter:
calls = 0
def fib_naive(n):
global calls
calls += 1
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(30), calls) # 832040 2692537
Computing fib(30) makes over 2.6 million calls, because fib(28), fib(27) and so on are recomputed from scratch in many branches. The call count grows exponentially with n.
Memoization (top-down)
Keep the recursion, add a cache. In Python the shortest way is functools.lru_cache:
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def fib_memo(n):
global calls
calls += 1
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(30), calls) # 832040 31
Now the body runs only 31 times, once for each value from 0 to 30. If you prefer an explicit dictionary, pass it in or create it inside an outer function. Avoid the common def f(n, memo={}) pattern: the default dictionary is created once and shared by every call to the function, so it works by accident here but leaks state between calls if the function depends on anything besides n.
Memoization computes only the states the recursion actually reaches. If most states are never needed, that is a real saving.
Tabulation (bottom-up)
Instead of recursing from the top, fill a table from the base cases:
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]
print(fib_tab(30)) # 832040
No recursion, so no call overhead and no recursion limit. The price is that you must work out the evaluation order yourself, and you compute every state in the table whether or not the answer needs it.
Shrinking the table
Each Fibonacci value depends only on the previous two, so the full table is wasteful:
def fib_opt(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_opt(30)) # 832040
This is O(n) time and O(1) space. Space optimization is the one real advantage tabulation has over memoization: because you control the order, you know when a state is no longer needed and can drop it. Grid problems are the usual case. In “Unique Paths”, each row of the table depends only on the row above, so one row is enough:
def paths_1d(rows, cols):
row = [1] * cols
for _ in range(1, rows):
for j in range(1, cols):
row[j] += row[j - 1]
return row[-1]
print(paths_1d(3, 7)) # 28
print(paths_1d(10, 10)) # 48620
A fuller example: coin change
Given coin denominations and a target amount, find the fewest coins that sum to the amount, or -1 if impossible. State: best(rem) is the fewest coins to make rem. Recurrence: best(rem) = 1 + min(best(rem - c)) over all coins c. Base case: best(0) = 0.
Top-down:
from functools import lru_cache
def coin_change_memo(coins, amount):
@lru_cache(maxsize=None)
def best(rem):
if rem == 0:
return 0
if rem < 0:
return float("inf")
return 1 + min((best(rem - c) for c in coins), default=float("inf"))
ans = best(amount)
return -1 if ans == float("inf") else ans
Bottom-up:
def coin_change_tab(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return -1 if dp[amount] == INF else dp[amount]
for coins, amt in [([1, 2, 5], 11), ([2], 3), ([1, 5, 10, 25], 63)]:
print(coins, amt, coin_change_memo(coins, amt), coin_change_tab(coins, amt))
# [1, 2, 5] 11 3 3
# [2] 3 -1 -1
# [1, 5, 10, 25] 63 6 6
Both are O(amount x number of coins) time and O(amount) space. A greedy “take the biggest coin first” approach fails on some coin sets, which is the reason this problem needs DP. For example, with coins 1, 3 and 4, greedy makes 6 as 4+1+1 (three coins) while DP finds 3+3 (two). The coin change walkthrough goes deeper.
The recursion limit is a real difference
CPython limits recursion depth (1,000 by default). A memoized function whose recursion is as deep as the input will hit it:
print(coin_change_tab([1], 5000)) # 5000
print(coin_change_memo([1], 5000)) # RecursionError
The tabulated version handles it, while the memoized one fails because it recurses 5,000 levels deep. You can raise the limit with sys.setrecursionlimit, but very deep recursion can still crash the interpreter, so for large inputs prefer tabulation. In Java and C++ the same issue shows up as a stack overflow. Interview inputs are usually small enough that this does not matter, but it is worth a sentence if the interviewer asks about constraints.
Memoization vs tabulation
| Memoization | Tabulation | |
|---|---|---|
| Direction | Top-down, recursive | Bottom-up, iterative |
| Writing it | Usually a direct translation of the recurrence | You must choose the fill order |
| States computed | Only the reachable ones | All states in the table |
| Stack depth | Can hit the recursion limit | None |
| Space optimization | Hard; the cache holds everything | Easy when states depend on a few recent ones |
| Overhead | Function calls and hashing | Plain loops and array indexing |
Neither is “more efficient” in the big-O sense. Many sources claim tabulation always uses less space; that is only true once you apply the rolling-row trick, since a plain table is the same size as the cache.
Which to use
- In an interview, start with whichever you can get correct fastest. For most people that is memoization, because you write the brute-force recursion first and add the cache.
- Switch to tabulation if the interviewer asks about recursion depth, or you want to cut the space to O(1) or a single row.
- Prefer memoization when only a small part of the state space is reachable (some subset and game problems).
Common mistakes
- Caching on the wrong key. The cache key must include every argument that affects the result. Forgetting one gives wrong answers that look right on small tests.
- A state that is too big. If your state has more dimensions than needed, the table gets huge. Ask whether each variable is really required.
- Base cases off by one. Check n = 0, n = 1, an empty input, and a target of 0 by hand.
- Unreachable states treated as 0. In minimization problems use infinity for “impossible”, not 0.
- Mutable arguments in a cached function.
lru_cacheneeds hashable arguments; pass tuples, not lists.
Practice
Do the same problem both ways: it is the fastest way to see how a recurrence turns into a loop. Good starting problems are climbing stairs, house robber, unique paths, coin change and longest common subsequence. AlgoCademy has a memoization lesson and a Unique Paths exercise where you build the table step by step. If DP still feels hard after that, why dynamic programming is so difficult to master explains where people usually get stuck.
