Tabulation
Learn how bottom-up dynamic programming fills a table iteratively to avoid recursion entirely.
Tabulation
Tabulation is the bottom-up approach to dynamic programming. Instead of starting at the final answer and recursing down (memoization), you start at the smallest subproblems and build up iteratively. The results are stored in a table — an array or 2D grid — that is filled one cell at a time until the final answer is computed.
dp[i] = minimum coins to make amount i
Fibonacci with tabulation — O(n) time, O(n) space
def fibonacci(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]
print(fibonacci(10)) # 55The table dp[i] holds the i-th Fibonacci number. Each cell depends only on the two cells before it. Fill left to right, done.
Space optimization — O(1) space
Since each cell only depends on the previous two, we only need to keep two variables:
def fibonacci(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fibonacci(50)) # 12586269025This reduces space from O(n) to O(1) — a common optimization once you identify which previous cells are actually needed.
Coin change with tabulation
def coin_change(coins, amount):
# dp[i] = minimum coins needed to make amount i
dp = [float("inf")] * (amount + 1)
dp[0] = 0 # base case — 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
print(coin_change([1, 5, 10, 25], 36)) # 3
print(coin_change([2], 3)) # -1Longest common subsequence (2D tabulation)
Some problems require a 2D table. LCS finds the longest sequence present in both strings, not necessarily contiguous.
def lcs(s1, s2):
m, n = len(s1), len(s2)
# dp[i][j] = LCS length of s1[:i] and s2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # characters match
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # take best
return dp[m][n]
print(lcs("ABCBDAB", "BDCAB")) # 4 → "BCAB" or "BDAB"Memoization vs tabulation — which to use
| Memoization | Tabulation | |
|---|---|---|
| Direction | Top-down | Bottom-up |
| Recursion | Yes | No |
| Stack overflow risk | Yes (deep recursion) | No |
| Only computes needed states | Yes (sparse) | No (fills whole table) |
| Space optimization | Harder | Straightforward |
| Easier to write first | Usually yes | Sometimes |
In interviews, memoization is often faster to write and easier to reason about. In production code, tabulation is usually preferred — no recursion limit risk, often faster due to cache locality, and space optimization is straightforward once the recurrence is known.
Complexity
| Problem | Time | Space (table) | Space (optimized) |
|---|---|---|---|
| Fibonacci | O(n) | O(n) | O(1) |
| Coin change | O(n × coins) | O(n) | O(n) — cannot reduce further |
| LCS | O(m × n) | O(m × n) | O(min(m, n)) |