Tabulation: Bottom-Up DP

"Memoization recurses down and remembers. Tabulation flips it: start from the smallest answers and build up, filling a table until the big answer falls out. Same DP, opposite direction, and no recursion at all."

Build Up Instead of Recursing Down

Tabulation is bottom-up dynamic programming. Instead of starting at the big problem and recursing toward the base cases, you start at the base cases and iteratively fill a table forward, computing each entry from entries you've already filled, until you reach the answer you wanted. There's no recursion — it's a plain loop over a table. The base cases are the seed; the final cell is the result. Fibonacci bottom-up: dp[0]=0, dp[1]=1, then loop dp[i] = dp[i-1] + dp[i-2] up to n.

The One New Challenge: Fill Order

The catch tabulation introduces is order: you must fill the table so that whenever you compute an entry, everything it depends on is already there. For Fibonacci that's trivially left-to-right. For a 2D DP (like edit distance), it means filling row by row, or in whatever order respects the dependencies. Memoization handled ordering automatically (the recursion computes dependencies on demand); tabulation makes you think it through. That's the trade: tabulation asks more design effort up front, in exchange for losing the recursion.

Tabulation = bottom-up DP: seed the base cases, then iteratively fill a table forward (each entry from already-computed ones) until you reach the answer. No recursion (no stack limit), often faster, but you must choose a fill order that respects dependencies — and it computes every state, even unneeded ones.

The Space Win: Keep Only What You Need

Tabulation unlocks a beautiful optimization memoization can't easily match. Often each table entry depends only on the last row or the last couple of cells — so you don't need the whole table in memory, just a sliding window of it. Fibonacci needs only the previous two values, so a full O(n) table collapses to two variables, O(1) space. Many 2D DPs that look like they need an O(n×m) grid actually only need the previous row, dropping space to O(m). Spotting 'I only depend on the last K cells' is how DP space costs shrink dramatically — a recurring trick worth looking for every time.

Memoization or Tabulation?

They compute the same answers; choose by constraints. Memoization: easier to write (cache a recursion), lazy (only needed states), but recursion-depth-bounded. Tabulation: no recursion limit, often faster, enables the space optimization above, but you must design the fill order and it computes all states. A common workflow: prototype with memoization to get the recurrence right, then convert to tabulation if you need the depth-safety or the space savings. Same DP, picked for the situation.

Pippa's Confession

I had a memoized DP that kept hitting the recursion limit on large inputs. I tried raising the limit (the trap from the recursion track) before Dad redirected me: convert it to a bottom-up table — no recursion, no limit. Rewriting it forced me to think about fill order, which I'd never had to before, and that's when DP truly clicked: memoization had been hiding the dependency structure from me. Tabulation made me see the shape of the computation, not just trust the recursion to find it.

Code

Tabulation, the space trick, and coin change·python

# TABULATION: build the answer up from base cases, no recursion.
def fib_table(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1            # base cases seed the table
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # each entry from already-filled ones
    return dp[n]

# SPACE-OPTIMIZED: each entry needs only the last TWO, so drop the table.
def fib_two_vars(n):              # O(1) space instead of O(n)
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b           # slide the window of two values forward
    return a

print(fib_table(10), fib_two_vars(10))   # 55 55

# Coin change, bottom-up: dp[a] = fewest coins to make amount a.
def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount      # dp[0]=0; rest unknown
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a-c] + 1)   # fill forward in order
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 3, 4], 6))   # 2 — same answer as the memoized version

Exercise

Convert the 'climbing stairs' DP (ways(n) = ways(n-1) + ways(n-2)) from memoization to bottom-up tabulation. Write the fill order and the base cases. Then space-optimize it to O(1) — what do you keep instead of the full table, and why is that enough?

Hint

Tabulation: dp[0]=1, dp[1]=1, then for i from 2 to n: dp[i]=dp[i-1]+dp[i-2], left to right (each depends only on earlier cells). Space-optimize: since dp[i] needs only the previous two values, keep two variables (a, b) and slide them forward — O(1) space, because nothing older than the last two is ever read again.

Build Up Instead of Recursing Down

The One New Challenge: Fill Order

The Space Win: Keep Only What You Need

Memoization or Tabulation?

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0