Tabulation (Bottom-Up DP)

Tabulation is the bottom-up way to do dynamic programming: instead of recursing from a big problem down to trivial base cases, you start at the base cases and iteratively build a table of subproblem answers until you reach the answer to the original problem. It trades the elegance of recursion for the predictability of a loop — no call stack, no risk of hitting Python’s recursion limit, and full control over exactly which subproblems get computed and in what order. Most classic DP problems (Fibonacci, climbing stairs, coin change, knapsack, longest common subsequence) can be solved this way, and in interviews it’s often the version you’re expected to produce once you’ve explained the recursive idea.

Overview / How it works

Every dynamic programming problem breaks down into overlapping subproblems, each identified by some "state" (often one or more indices). Memoization solves this top-down: you write the natural recursive solution and cache results as you go. Tabulation flips the direction — you decide in advance every subproblem you’ll ever need, store them in a table (usually a list or 2D list), fill in the smallest ones first (the base cases), and use the recurrence relation to compute each larger subproblem from the smaller ones already sitting in the table.

Take Fibonacci numbers as the simplest example. The recursive definition is fib(n) = fib(n-1) + fib(n-2) with base cases fib(0) = 0 and fib(1) = 1. A naive recursive implementation recomputes the same subproblems exponentially many times. Tabulation instead builds a list table of size n + 1, seeds table[0] and table[1] with the base cases, and walks forward from index 2 to n, filling each slot using the two slots directly before it. By the time the loop reaches index n, every value it needs has already been computed and stored — that’s the defining trait of bottom-up DP: you never ask for an answer that hasn’t been built yet.

The four steps of tabulation

1. Define the state. What does one cell of the table represent? For Fibonacci it’s "the nth Fibonacci number." For knapsack it’s "the best value achievable using the first i items with capacity w."
2. Size the table to match every possible state, usually with size n + 1 (or (n + 1) x (capacity + 1) for two dimensions) so indices line up directly with problem sizes and you never need an awkward index shift.
3. Seed the base cases — the smallest subproblems whose answers you already know without needing the recurrence.
4. Fill the table in an order that guarantees dependencies come first, applying the recurrence relation at each step, until you reach the cell that answers the original question.

That fourth step is where beginners trip up most often: the fill order has to match the dependency direction of the recurrence. If table[i] depends on table[i-1], you must fill in increasing order of i; if a compressed version depended on values not yet overwritten, you might need to go backwards instead. Get this wrong and you’ll either read a slot that’s still at its initial value (a silently wrong answer) or read past the end of the table (a crash) — both appear in Common Mistakes below.

Time and Space Complexity

Problem	State	Time	Space (naive / optimized)
Fibonacci	1D: index n	O(n)	O(n) / O(1)
Climbing stairs	1D: index n	O(n)	O(n) / O(1)
0/1 Knapsack	2D: item index × capacity	O(n · W)	O(n · W) / O(W)

In general, tabulation’s time complexity is the number of distinct states multiplied by the work done to fill each one. For 1D problems like Fibonacci that’s O(n) states × O(1) work per state = O(n) overall — compare that to naive recursive Fibonacci, which is O(2^n) because it recomputes the same subproblems over and over with no cache. For 2D problems like 0/1 knapsack with n items and capacity W, there are O(n · W) cells, each filled in O(1) time by comparing two candidate values, giving O(n · W) time and, if you keep the full grid, O(n · W) space.

Space is where tabulation has a genuine edge over memoization. Because you fill the table in a fixed order and each state usually depends only on a small, predictable window of previous states (the row directly above, or the last two entries), you can often throw away everything outside that window. Fibonacci needs only the last two numbers, not the whole array, so it can run in O(1) space; 0/1 knapsack only ever needs the previous row, so it can be compressed from O(n · W) down to O(W). Memoization’s recursion, by contrast, keeps the entire call stack alive and generally can’t be trimmed the same way.

Examples

Example 1: Fibonacci numbers

The simplest tabulation example: build a table of Fibonacci numbers from the two base cases upward.

def fib(n: int) -> int:
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


result = fib(10)
print(result)

Output:

55

Tracing it: table starts as eleven zeros, then table[1] is set to 1. The loop walks from index 2 to 10, and each entry is the sum of the two before it: 1, 2, 3, 5, 8, 13, 21, 34, 55. By the time i reaches 10, table[10] holds 55, which is exactly the 10th Fibonacci number.

Example 2: Climbing stairs

A classic interview problem: you can climb 1 or 2 steps at a time — how many distinct ways are there to reach the top of an n-step staircase? The recurrence is identical in shape to Fibonacci: the number of ways to reach step i is the ways to reach i-1 (then take one step) plus the ways to reach i-2 (then take two steps).

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    table[2] = 2
    for i in range(3, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


result = climb_stairs(5)
print(result)

Output:

8

With table[1] = 1 and table[2] = 2 seeded, the loop fills table[3] = 3, table[4] = 5, and table[5] = 8. There are 8 distinct ways to climb 5 stairs taking one or two steps at a time.

Example 3: 0/1 Knapsack

A more realistic, two-dimensional tabulation problem. Given items with weights and values and a capacity limit, find the maximum total value you can carry without exceeding the capacity, using each item at most once. The state is table[i][w] = the best value achievable using the first i items with capacity w.

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    table = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                table[i][w] = max(table[i - 1][w], values[i - 1] + table[i - 1][w - weights[i - 1]])
            else:
                table[i][w] = table[i - 1][w]
    return table[n][capacity]


weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
result = knapsack(weights, values, capacity)
print(result)

Output:

9

Row 0 (no items available) is all zeros. Each later row either carries down the value from the row above (the current item doesn’t fit or isn’t worth including) or takes the current item’s value plus whatever fit in the leftover capacity. The full row-by-row trace is worked out in the next section.

How it works step by step

Let’s trace the knapsack table from Example 3 cell by cell, using weights = [1, 3, 4, 5], values = [1, 4, 5, 7], and capacity = 7.

Items considered	w=0	w=1	w=2	w=3	w=4	w=5	w=6	w=7
0: none	0	0	0	0	0	0	0	0
1: weight 1, value 1	0	1	1	1	1	1	1	1
2: weight 3, value 4	0	1	1	4	5	5	5	5
3: weight 4, value 5	0	1	1	4	5	6	6	9
4: weight 5, value 7	0	1	1	4	5	7	8	9

Row 1 introduces the weight-1/value-1 item: any capacity of at least 1 can hold it, so every column from w=1 onward becomes 1. Row 2 introduces weight-3/value-4: at w=3 the value jumps to 4 (take the item alone), and at w=4 it reaches 5 (the item plus the leftover capacity-1 slot filled by item 1). Row 3 introduces weight-4/value-5, and the interesting jump is at w=7: table[3][7] = max(table[2][7], 5 + table[2][3]) = max(5, 5 + 4) = 9 — taking item 3 and filling the remaining capacity 3 with item 2 beats anything found so far. Row 4 introduces weight-5/value-7: at w=5 it improves to 7 (item 4 alone beats the previous 6), and at w=6 it improves to 8 (item 4 plus the weight-1 item). But at w=7, taking item 4 plus whatever fits in the remaining capacity 2 gives 7 + table[3][2] = 7 + 1 = 8, which is worse than the 9 already found, so the cell keeps its previous value. The final answer, table[4][7] = 9, is read directly out of the bottom-right corner of the table.

Common Mistakes

Mistake 1: Off-by-one table size and fill range

Two related bugs come from getting the table’s size or the loop’s starting index wrong. First, sizing the table to n instead of n + 1 means the last valid index is n - 1, but the recurrence still tries to write table[n]:

def fib(n: int) -> int:
    table = [0] * n
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(fib(6))

This raises IndexError: list index out of range the moment i reaches n, because a list of length n only has valid indices 0 through n - 1.

Second, and more dangerous because it fails silently, starting the fill loop at the wrong index can make Python’s negative-indexing quietly return garbage instead of crashing:

def fib(n: int) -> int:
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(1, n):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(fib(6))

On the very first iteration, i = 1, so the code evaluates table[i - 2], which is table[-1] — Python happily interprets that as the last element of the list rather than raising an error, silently overwriting table[1] with 0. Worse, the loop’s upper bound range(1, n) stops one short, so table[n] is never assigned at all and the function returns its untouched initial value, 0, instead of the correct Fibonacci number.

The fix is to size the table to n + 1 and start the fill loop at index 2 (the first index whose two predecessors are real, non-negative indices):

def fib(n: int) -> int:
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


print(fib(6))

Output:

8

Mistake 2: Filling the capacity dimension in the wrong direction after compressing 0/1 knapsack to 1D

It’s tempting to compress the 2D knapsack table to a single 1D array of size capacity + 1, updating it in place for each item. But the direction you loop over capacities matters enormously. Looping forward lets an item’s own update feed into a later cell in the same pass, which effectively allows that item to be reused — turning 0/1 knapsack into unbounded knapsack:

def knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    table = [0] * (capacity + 1)
    for i in range(n):
        for w in range(weights[i], capacity + 1):
            table[w] = max(table[w], values[i] + table[w - weights[i]])
    return table[capacity]


print(knapsack_1d([2, 3], [3, 4], 6))

With weights [2, 3], values [3, 4], and capacity 6, this prints 9 — but that answer comes from taking the weight-2 item three times (weight 6, value 9), which isn’t a valid 0/1 knapsack solution since each item may only be used once. The correct 0/1 answer, using each item at most once, is 7 (both items together: weight 5, value 7).

The fix is to iterate the capacity dimension backward, from capacity down to the item’s weight. That guarantees every cell an item’s update reads from still holds a value computed before that item was considered, so the item can’t be counted twice:

def knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    table = [0] * (capacity + 1)
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            table[w] = max(table[w], values[i] + table[w - weights[i]])
    return table[capacity]


print(knapsack_1d([2, 3], [3, 4], 6))

Output:

7

Best Practices

• Size your table so indices map directly to problem sizes (usually length n + 1) to avoid off-by-one bugs and awkward index shifting.
• Initialize base cases explicitly, rather than relying on default zeros to happen to be correct for every problem — for "minimum coins"-style problems, unreachable states usually need a large sentinel value, not zero.
• Choose the fill order deliberately: forward when a state depends on smaller-indexed states already in the table; backward when compressing to a 1D array and each item may only be used once.
• Prefer tabulation over memoization when n is large enough that recursion depth or call-stack overhead is a concern, or when the table can be compressed to save memory.
• Prefer memoization when the state space is sparse (most states are never actually visited) — tabulation computes every cell whether it’s needed or not, while memoization computes only reachable states.
• Once a tabulated solution is correct, look for a space optimization (rolling array or a couple of scalar variables) before calling it done — most 1D and many 2D tabulation solutions can shed a full dimension.
• When debugging, print or log the table’s state after each row or iteration — DP bugs are almost always index-math bugs, not algorithmic ones.

Practice Exercises

1. House Robber. Given a list of nonnegative integers representing money stashed in houses arranged in a line, find the maximum amount you can rob without robbing two adjacent houses. Solve it bottom-up. Hint: define table[i] as the best amount using only the first i houses, with table[i] = max(table[i - 1], table[i - 2] + nums[i - 1]). For nums = [2, 7, 9, 3, 1], the answer should be 12.

2. Coin Change (minimum coins). Given a list of coin denominations and a target amount, find the fewest coins needed to make that amount, or determine it’s impossible. Solve it bottom-up. Hint: initialize the table with a large sentinel value everywhere except table[0] = 0, since making 0 always costs 0 coins.

3. Space-optimize the knapsack. Take the 2D knapsack from Example 3 and rewrite it as a 1D array (as shown in Common Mistakes), but for a new set of weights and values of your choosing. Run both versions on the same inputs and confirm they return the same final value.

Summary

• Tabulation solves DP problems bottom-up: fill a table starting from base cases and use a recurrence to build up to the final answer, with no recursion involved.
• Follow four steps: define the state, size the table to match every state, seed the base cases, and fill the table in a dependency-safe order.
• Time complexity is number of states × work per state — O(n) for 1D Fibonacci-style problems, O(n · W) for 2D knapsack-style problems.
• Space is often compressible: 1D problems can frequently run in O(1) space by keeping only the last few values, and 2D problems can often drop to O(W) by keeping only the previous row.
• The most common bugs are index math: undersized tables, wrong loop starting bounds, and (for space-optimized 0/1 knapsack specifically) filling the capacity dimension in the wrong direction.
• Reach for tabulation when the state space is small and dense and you want to avoid recursion limits; reach for memoization when the state space is large but sparse.