Tabulation (Bottom-Up DP)
DSA · Dynamic Programming
Theory
Tabulation solves a dynamic programming problem by filling a table iteratively, starting from the smallest subproblems and building up to the answer. Instead of recursion, you decide an order in which every subproblem's dependencies are already computed, then loop through that order. For Fibonacci, table[0] = 0, table[1] = 1, and each later cell is the sum of the two before it. Because there is no recursion, there is no stack overflow risk and no function-call overhead, and you can often reduce memory by keeping only the last few rows or values. The steps are always the same: define what table[i] means, write the recurrence, set base cases, choose the fill order, and read the final answer from the table.
Why we use it
Bottom-up DP is usually faster than memoised recursion, avoids recursion depth limits, and makes space optimisation (keeping only what is needed) straightforward.
When to use it
Use tabulation when you will need most subproblems anyway, when inputs are large enough that recursion could overflow, or when you want to optimise memory.
How it works
- Create table with base cases
- For each state in dependency order
- table[state] = recurrence(earlier states)
- Return the final cell
Syntax
table = [base values]
for i in fill order:
table[i] = recurrence(table[smaller i])
return table[target]Example
# 1. Fibonacci with a table, then with O(1) memory
def fib_table(n):
t = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
t[i] = t[i - 1] + t[i - 2]
return t[n]
def fib_two_vars(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_table(50), fib_two_vars(50))
# 2. Minimum cost path in a grid (move right or down)
cost = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1],
]
R, C = len(cost), len(cost[0])
dp = [[0] * C for _ in range(R)]
for r in range(R):
for c in range(C):
if r == 0 and c == 0:
dp[r][c] = cost[r][c]
else:
up = dp[r - 1][c] if r else float("inf")
left = dp[r][c - 1] if c else float("inf")
dp[r][c] = cost[r][c] + min(up, left)
for row in dp:
print(row)
print("Minimum path cost:", dp[-1][-1])Key points
- Fill a table from base cases upward
- No recursion, so no stack overflow
- Often allows O(1) or O(n) memory optimisation
- Same recurrence as memoization, different evaluation order