Algorithms from zero
Tabulation: bottom-up DP, the table
Last lesson, memoization computed each Fibonacci subproblem once by caching a recursion. It works, but it still recurses: fib(n) calls down to fib(0) before anything returns, and that chain of unfinished calls is a stack that can get deep enough to crash. Now flip the whole thing upside down. Instead of starting at the goal and recursing down, start at the base cases and build up. Lay out a row of boxes—one per subproblem. Write the two answers you already know, fib(0) and fib(1). Then walk the row left to right with a plain loop, filling each box from the two before it. No recursion, no stack, and when you reach the last box you have your answer. That is tabulation: bottom-up DP, the table.
After this lesson you can implement dynamic programming bottom-up with tabulation. You can name the four pieces every tabulated DP needs: the dp array and what each cell means, the base cases that seed it, the transition (the recurrence in array form), and the iteration order that guarantees every cell is filled before anything reads it. You can convert a memoized (top-down) solution into a tabulated (bottom-up) one for both Fibonacci and climbing stairs. You can contrast the two directions: tabulation pays no recursion-stack cost and runs in a predictable order, but it computes every state even ones a top-down run would skip; memoization computes only reachable states but pays a stack and hashing. You can apply space optimization: when a cell only depends on the last few cells, keep just those in a rolling window and drop the whole table, taking Fibonacci’s space from O(n) to O(1). This closes the DP basics; later lessons apply the table to harder recurrences.
What is tabulation?
Tabulation is the bottom-up way to write dynamic programming. Instead of a recursion that starts at the goal and descends to the base cases, you create a table—usually an array called dp—fill in the base cases directly, then run a loop that fills the rest of the table in an order where every cell you compute reads only cells that are already filled. When the loop finishes, the answer is sitting in the cell for the goal. There is no recursion and no call stack.
The four pieces of every tabulated DP
A tabulated solution is always the same four decisions. Get these right and the code writes itself:
- The dp array and its meaning. Decide what
dp[i]stands for. For Fibonacci,dp[i]is “the i-th Fibonacci number.” Writing this meaning down in one sentence is the most important step—everything else follows from it. - The base cases. The cells you can fill with no computation. For Fibonacci:
dp[0] = 0anddp[1] = 1. - The transition (the recurrence). How to compute a non-base cell from earlier cells. For Fibonacci:
dp[i] = dp[i - 1] + dp[i - 2]. This is the exact same recurrence the recursion used, just reading the array instead of making calls. - The iteration order. The order to fill cells so that when you compute
dp[i], every cell it depends on is already done. For Fibonacci,dp[i]needsdp[i-1]anddp[i-2], so filling left to right (i from 2 up to n) guarantees both are ready.
Why iteration order is the whole trick
Memoization never worried about order—the recursion discovered the order on demand. Tabulation has no recursion to discover anything, so you must pick an order that respects the dependencies. The rule is simple: a cell may only depend on cells filled earlier in the loop. For Fibonacci the dependency points backward (i needs i-1 and i-2), so going forward from the base cases satisfies it. If you got the order wrong—say you tried to fill dp[i] before dp[i-1] existed—you would read an empty cell and get garbage.
Tabulation as the same recurrence, run forward
Memoization and tabulation solve the identical recurrence with the identical base cases. The only difference is direction:
memoization (top-down): start at fib(n), recurse DOWN to fib(0), fill cache on the way back up
tabulation (bottom-up): start at fib(0), loop UP to fib(n), fill the table left to rightWatch the table fill, left to right
For fib, dp starts with the two base cases, and each step adds the sum of the two cells to its left. The ”?” marks cells not yet computed:
seed bases: dp = [0, 1, ?, ?, ?, ?, ?, ?]
i = 2: dp[2] = dp[1] + dp[0] = 1 -> [0, 1, 1, ?, ?, ?, ?, ?]
i = 3: dp[3] = dp[2] + dp[1] = 2 -> [0, 1, 1, 2, ?, ?, ?, ?]
i = 4: dp[4] = dp[3] + dp[2] = 3 -> [0, 1, 1, 2, 3, ?, ?, ?]
i = 5: dp[5] = dp[4] + dp[3] = 5 -> [0, 1, 1, 2, 3, 5, ?, ?]
i = 6: dp[6] = dp[5] + dp[4] = 8 -> [0, 1, 1, 2, 3, 5, 8, ?]
i = 7: dp[7] = dp[6] + dp[5] = 13 -> [0, 1, 1, 2, 3, 5, 8, 13]
answer: dp[7] = 13Each cell is computed exactly once, in one clean left-to-right pass. No cell is ever read before it is written, because the loop order matches the dependency direction.
The cost of going bottom-up
Tabulation computes every cell from the base cases up to the goal, whether or not a top-down run would have needed it. For a dense problem like Fibonacci that is no loss—every cell is needed anyway. But if the reachable states were sparse (imagine a recursion that only ever touches a scattered few of the possible states), memoization would compute just those, while tabulation would fill the whole range. That is the tradeoff you accept in exchange for losing the recursion stack.
Tabulated Fibonacci (bottom-up)
This is the same recurrence and base cases as the memoized version from lesson 02, but driven by a loop over an array instead of a recursion over a cache.
1
function fib(n) {
2
// Base cases handled directly
3
if (n <= 1) {
4
return n;
5
}
6
// dp[i] means "the i-th Fibonacci number"
7
const dp = new Array(n + 1);
8
dp[0] = 0; // base case
9
dp[1] = 1; // base case
10
// Fill left to right: every cell reads two already-filled cells
11
for (let i = 2; i <= n; i++) {
12
dp[i] = dp[i - 1] + dp[i - 2]; // the transition (recurrence)
13
}
14
// The goal is the last cell
15
return dp[n];
16
}
- L3 Guard the tiny inputs so dp[1] is always a valid index when we build the array.
- L7 The dp array: one cell per subproblem, indices 0..n. dp[i] = the i-th Fibonacci number.
- L8 Base case dp[0] = 0, filled with no computation.
- L9 Base case dp[1] = 1, filled with no computation.
- L11 Iteration order: i goes from 2 up to n, so dp[i-1] and dp[i-2] are always already filled.
- L12 The transition: each cell is the sum of the two cells to its left. Same recurrence as the recursion, reading the array.
- L15 After the loop, dp[n] holds the answer. No recursion, no stack.
Key point: no recursion stack
The whole function is one loop. Nothing calls itself, so there is no chain of unfinished calls and no call stack to grow. For very large n, the memoized version could overflow the stack on its first deep descent; the tabulated version never can—it just iterates.
Running it: the filled table and the answers
The printed table is exactly the row we filled by hand. The loop did the same left-to-right pass.
Space optimization: the rolling window
Look at the transition again: dp[i] = dp[i - 1] + dp[i - 2]. To compute any cell, you only ever need the last two cells. Once dp[i] is computed, dp[i - 2] is never read again. So storing the whole array is wasteful—you can keep just the last two values in two variables and slide them forward. This rolling window takes Fibonacci’s space from O(n) down to O(1) while keeping the same O(n) time.
1
function fib(n) {
2
if (n <= 1) {
3
return n;
4
}
5
// Keep only the two cells the transition needs
6
let prev2 = 0; // plays the role of dp[i - 2], starts at fib(0)
7
let prev1 = 1; // plays the role of dp[i - 1], starts at fib(1)
8
for (let i = 2; i <= n; i++) {
9
const curr = prev1 + prev2; // the same transition, on the two kept values
10
prev2 = prev1; // slide the window forward
11
prev1 = curr;
12
}
13
return prev1; // prev1 now holds fib(n)
14
}
- L6 prev2 holds fib(i-2). It starts as fib(0) = 0.
- L7 prev1 holds fib(i-1). It starts as fib(1) = 1.
- L9 Same transition as the array version, but reading the two kept variables.
- L10 Slide the window: the old prev1 becomes the new prev2.
- L11 And the freshly computed value becomes the new prev1.
- L13 After the loop prev1 is fib(n). We never stored the whole table: O(1) space.
Same answers, one constant slice of memory. Space optimization works whenever the transition reaches back only a fixed number of cells.
A second example: climbing stairs, tabulated
The climbing-stairs recurrence from lesson 02 is ways(n) = ways(n-1) + ways(n-2)—the same shape as Fibonacci, with base cases ways(1) = 1 and ways(2) = 2. So the table version is the same machinery: a dp array, two base cells, the transition, a left-to-right loop. And because the transition again reaches back only two cells, the rolling-window optimization applies just as it did for fib.
Both versions agree. Once you can name the four pieces—array, base cases, transition, order—converting any memoized DP to a table is mechanical, and shrinking the space is a matter of asking how far back the transition reaches.
Let us trace the tabulated fib for n = 5 and watch the cells fill left to right. The dp array starts with only the base cases written; each frame computes one more cell from the two to its left. ”?” marks a cell not yet filled.
1
function fib(n) {
2
if (n <= 1) return n;
3
const dp = new Array(n + 1);
4
dp[0] = 0;
5
dp[1] = 1;
6
for (let i = 2; i <= n; i++) {
7
dp[i] = dp[i - 1] + dp[i - 2];
8
}
9
return dp[n];
10
}
Time: O(n)
The loop runs once per cell from i = 2 to i = n, and each iteration does O(1) work (one addition, one assignment). That is n − 1 iterations of constant work, so O(n). This matches memoization exactly, and for the same reason: the general DP rule is
total time = (number of distinct states) x (work per state)For Fibonacci that is (n+1) states x O(1) work = O(n), whether you reach the states by recursing down or by looping up.
Space: O(n) with the full table, O(1) with the rolling window
The naive tabulation stores one cell per state in the dp array: O(n). But the recursion stack that memoization paid is gone—the loop has no call depth—so tabulation’s space is just the table, with no extra O(n) stack term.
Better still: the transition dp[i] = dp[i-1] + dp[i-2] reaches back only two cells, so you never need the whole array at once. Keep the last two values in two variables and the space drops to O(1) while the time stays O(n). This is the rolling-window optimization, and it applies to any DP whose transition depends only on a fixed number of recent states.
time space (table) space (rolling) stack
memoization O(n) O(n) cache — O(n) <- last lesson
tabulation O(n) O(n) table O(1) none <- this lessonWhen tabulation wins, and when it does not
Tabulation’s advantages are no recursion-stack cost (so no stack-overflow risk for huge n), a predictable fixed iteration order, and the easy path to O(1) space when the transition reaches back only a little. Its cost is that it computes every cell from the base cases to the goal, even cells a top-down run would have skipped. For dense problems like fib that costs nothing—every cell is needed. For sparse, scattered state spaces, memoization’s “only compute what you reach” can do strictly less work. Pick the direction that fits the problem; the recurrence and the O(n) time are the same either way.
What is the defining feature of tabulation compared with memoization?
In a tabulated DP, why does the iteration order matter?
For tabulated Fibonacci, what is the transition that fills a non-base cell dp[i]?
Why can Fibonacci's tabulation be optimized from O(n) space to O(1) space?
Which cost does tabulation avoid that top-down memoization pays?
What is one disadvantage of tabulation compared with memoization?
A tabulated DP has 250 distinct states and does O(1) work per state. About how many cell computations does the loop perform in total?
Why this works
Why learn tabulation if memoization already works? Three reasons. First, no recursion stack: for very large n a top-down run can overflow the call stack, while a loop never can. Second, predictability: the fixed iteration order is easy to reason about and has no per-call function overhead, so it is usually a bit faster in practice. Third, and most valuable, the table makes space optimization obvious—once you see the transition reaches back only a couple of cells, the rolling window that drops O(n) to O(1) almost writes itself. A common workflow is to write the recursion, memoize it to get a correct O(n) solution, then tabulate when you need the smaller stack or smaller space.
Common mistake
Mistake: filling the table in an order that reads empty cells. Tabulation has no recursion to discover the order, so a wrong loop direction reads cells that have not been written yet. If you tried to compute dp[i] before dp[i-1] existed, you would read undefined and produce NaN. Always check the dependency direction first: Fibonacci’s dp[i] depends on smaller indices, so the loop must go forward from the base cases. Some DPs depend on larger indices and must loop backward. Match the loop to the dependencies.
Edge cases
Tiny inputs and base cases. Guard the small inputs before building the array. For Fibonacci, if (n <= 1) return n; handles n = 0 and n = 1, so writing dp[1] = 1 is never an out-of-range index. For climbing stairs, if (n <= 2) return n; covers the two base cells. Skipping these guards is a classic off-by-one bug: building a length-n+1 array and then assuming dp[1] exists when n is 0 writes past a one-element array.
More practice
The recipe for any tabulated DP. (1) Define dp[i] in one sentence—what does the cell mean? (2) Fill the base cases directly, with no computation. (3) Write the transition: how a non-base cell is built from earlier cells (it is the same recurrence the recursion used). (4) Pick the iteration order so every cell is filled before it is read—forward when dependencies point to smaller indices. (5) Ask how far back the transition reaches; if only a fixed few cells, replace the array with rolling variables for O(1) space. Try the recipe on climbing stairs above, then on min-cost climbing stairs.
Explain what tabulation is, the four pieces it needs, why iteration order matters, how it compares with memoization, and how the rolling-window optimization works.
Tabulation is the bottom-up way to write dynamic programming: build a dp array, fill the base cases, then loop from small states up to the goal. No recursion, no call stack.
The four pieces:
- The dp array and its meaning — decide in one sentence what
dp[i]stands for (for fib, “the i-th Fibonacci number”). - The base cases — the cells you fill with no computation (
dp[0] = 0,dp[1] = 1). - The transition (recurrence) — how a non-base cell is built from earlier cells (
dp[i] = dp[i-1] + dp[i-2]). - The iteration order — fill cells so that every cell is computed before anything reads it. Forward when dependencies point to smaller indices.
Bottom-up vs top-down: tabulation loops up from the base cases; memoization recurses down from the goal. Same recurrence, same O(n) time. Tabulation pays no recursion stack (no overflow for large n) but computes every state in the range, even ones a top-down run would skip.
Space optimization (rolling window): when the transition reaches back only a fixed number of cells, keep just those in variables and drop the table. For Fibonacci that takes space from O(n) to O(1) with the same O(n) time.
That closes the DP basics: a problem, a recurrence, a cache or a table. Memoize when only a sparse set of states is reachable or the order is hard to plan; tabulate when you want no stack, a predictable order, or O(1) space.