From asking to filling
In the last guide you took the naive recursion that wastefully recomputed overlapping subproblems and tamed it with memoization: you kept the recursive shape, but parked each answer in a cache the moment you first computed it, so the second request for the same subproblem was a free lookup. Tabulation, also called bottom-up DP, reaches the same destination from the opposite direction. Instead of letting the recursion ask for subproblems and discovering on the way which ones it needs, you sit down ahead of time, list every subproblem, and fill in their answers in an order where each one is ready exactly when you need it.
Take the Fibonacci numbers, the toy example from the start of this rung. Memoization computes F(n) by recursing down to F(1) and F(0) and caching on the way back up. Tabulation flips it: make an array fib[0..n], write fib[0]=0 and fib[1]=1 by hand, then sweep a loop from i=2 upward computing fib[i]=fib[i-1]+fib[i-2]. Each entry reads only entries to its left, which are already filled. No recursion, no call stack, no cache-miss check — just a loop walking a table. That is the entire spirit of tabulation: replace the recursion with an explicit table and an explicit order of filling.
fib[0] = 0
fib[1] = 1
for i = 2 to n:
fib[i] = fib[i-1] + fib[i-2] # left-to-right: deps ready
return fib[n]Three things you must pin down
Tabulation is not free improvisation; it forces you to make three decisions explicit that memoization let you leave implicit. First, the table shape: how many dimensions and how big — one array indexed by i, a 2-D grid indexed by (i, j), and so on. Second, the base cases: the cells whose answers you fill by hand because they depend on nothing. Third, and the part that bites beginners, the evaluation order: the sequence in which you visit cells so that whenever you compute a cell, every cell it reads is already done.
That third point is the heart of tabulation and deserves a sharp picture. Think of every subproblem as a node, and draw an arrow from subproblem A to subproblem B whenever B's answer is needed to compute A. This is a dependency graph, and because subproblems only ever depend on smaller ones, it has no cycles — it is a DAG. A valid evaluation order is then exactly a topological ordering of that DAG: visit each node only after everything it points to is finished. For Fibonacci the DAG is a line and the topological order is simply 0, 1, 2, ..., n — which is why a plain left-to-right loop works.
A 2-D walkthrough: counting grid paths
Let us fill a real 2-D table. Count the number of paths from the top-left corner of an m-by-n grid to the bottom-right corner, moving only right or down. Define the state ways[i][j] = the number of such paths reaching cell (i, j). A path arrives at (i, j) either by stepping down from (i-1, j) or stepping right from (i, j-1), so the transition is ways[i][j] = ways[i-1][j] + ways[i][j-1]. The base cases are the top row and left column, where there is exactly one path (keep going straight), so every cell there is 1.
Now the order. Cell (i, j) reads the cell directly above and the cell directly to its left, so both of those must already be filled when we reach (i, j). A row-by-row sweep — outer loop over i from top to bottom, inner loop over j from left to right — satisfies exactly that: by the time we touch (i, j), row i-1 is wholly done and (i, j-1) was done one step earlier in the same row. That nested loop is a topological order of this grid's dependency DAG. Run it on a 3-by-3 grid and the interior fills as 1,1,1 / 1,2,3 / 1,3,6 — the bottom-right answer is 6 paths, and you can verify by hand.
Reconstructing the answer, and shrinking the table
A filled table usually gives you the value of the optimum — the count, the cost, the length — but often you want the actual object: the path, the chosen items, the aligned strings. The standard move is reconstruction by backtracking through the finished table. Start at the answer cell and, at each step, look at the transition: which predecessor cell did this value come from? Walk to that predecessor and repeat until you hit a base case. The trail you trace out, reversed, is the solution. In the grid above, from the bottom-right you would repeatedly step to whichever of (up) or (left) it was summed from, recovering one concrete path.
Tabulation also exposes a memory optimization that top-down hides. Because the grid's transition only ever reads the previous row (and the current row to the left), you never need all m rows in memory at once — two rows, or even one row updated carefully in place, suffice. That drops the space from O(m*n) to O(n) while the time stays O(m*n). This 'rolling array' trick is a signature advantage of bottom-up: when the dependency reach is shallow, you can throw away old layers of the table. The catch is honest and worth stating: once you collapse the table, you have thrown away the history reconstruction needs, so you keep the full table only when you must recover the object itself.
When bottom-up wins, when it loses
Tabulation and memoization compute the same DAG, so their asymptotic time is identical: in both, total time is (number of distinct subproblems) times (work per transition). What differs are the constants and the failure modes. Bottom-up usually wins on the constant factor — a tight loop over an array has no recursion overhead, no call stack, no hash-map cache lookups, and friendlier memory access patterns. It also cannot overflow the call stack, which a deep recursion can. And, as we just saw, it opens the door to rolling-array space savings.
But bottom-up has one real cost that the top-down approach quietly avoids: tabulation fills every cell in the table, whether or not the final answer depends on it. Memoization only ever computes the subproblems the recursion actually reaches. If the reachable subproblems are a sparse fraction of the full table — a common situation in coin-change or knapsack with awkward weights — top-down can be dramatically faster in practice even though both are the same Big-O, because Big-O counts the worst case and hides exactly this kind of constant. When the table is densely needed (Fibonacci, grid paths, edit distance), tabulation is the natural choice; when it is sparsely needed, memoization can save the wasted cells.
There is also a correctness pitfall unique to bottom-up, and it is worth naming plainly: a tabulation is only correct if your loop order is a genuine topological order of the dependency DAG. Get the order wrong — iterate a dimension the wrong way, or fill a cell before the cell it reads — and the code will run, return a number, and be silently wrong. Memoization is more forgiving here because it computes a dependency on demand the first time it is asked. So the single discipline that makes bottom-up safe is the one from this guide: write the transition, identify what each cell reads, and order the loops so reads always point backward into already-filled cells.