Tabulation
Fill a DP table from base cases upward (bottom-up), avoid Python's recursion limit, and cut space with a rolling array.
- Explain bottom-up DP (fill a table from base cases up to the answer)
- Compare tabulation with top-down memoisation on practical grounds
- Apply the rolling-array optimisation to reduce O(n) space to O(1)
Memoisation adds a cache to a recursive function. Tabulation removes the recursion entirely: fill an array from the smallest sub-problem to the largest, always using only values you have already computed.
The tabulation pattern
For Fibonacci, the recurrence is fib(n) = fib(n-1) + fib(n-2). In
tabulation, you allocate an array dp of size n+1 and fill it left to right:
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]The loop runs exactly n-1 times. There is no recursion and no cache lookup
overhead — just array reads and writes.
Top-down vs bottom-up: which to choose?
Both achieve the same asymptotic complexity. The practical differences matter in production code:
| Concern | Top-down (memoisation) | Bottom-up (tabulation) |
|---|---|---|
| Recursion limit | Can hit Python's default 1 000 limit for large n | No recursion — no limit |
| Clarity | Natural: mirrors the recurrence directly | Requires knowing the fill order |
| Lazy evaluation | Only solves sub-problems that are actually needed | Solves all sub-problems, needed or not |
| Space optimisation | Cache holds all seen values | Can sometimes keep only 1–2 rows |
For most interview-style problems, top-down is faster to write correctly. For production code processing large inputs, bottom-up is usually safer.
The rolling-array optimisation
fib_table above stores all n+1 values in dp. But the recurrence only
ever reads the two most recent values: dp[i-1] and dp[i-2]. Everything
before that is dead weight.
A rolling array (sometimes called a sliding window of size k) keeps only the k values needed by the recurrence, discarding the rest:
def fib_space_opt(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1Space drops from O(n) to O(1). The trade-off: you can no longer inspect intermediate values (useful for debugging), and reconstructing the full solution path (if needed) requires storing more.
The rolling-array trick generalises: if dp[i] depends only on the previous
row in a 2D table, keep two rows instead of the full table, halving memory.
This is important for large 2D problems like edit distance on long strings.
Choosing the fill order
Before writing a tabulation loop, answer: "which earlier cells does dp[i]
depend on?" Fill those first. For 1D Fibonacci the order is obvious: left to
right. For 2D problems (covered in a later lesson), the order is less
obvious and getting it wrong produces incorrect results.
Where to go next
Next: classic DP patterns — implementing coin change, 0/1 knapsack, and climbing stairs bottom-up, all running in the browser.