Top-Down vs Bottom-Up Dynamic Programming

The idea: one recurrence, two orders

A dynamic programming problem is a recurrence: the answer for a state is built from the answers for smaller states, down to a few base cases. Top-down code writes the recurrence as a recursive function plus a memo, a cache of answers already found. Bottom-up code (tabulation) fills a table dp with a loop, base cases first, in an order where every cell's inputs are already there. The canvas runs both on the same problem, one step each, and counts what each side computes. The interesting part is where they differ: how many states get computed, how deep the stack gets, and who decides the order.

Top-down computes only the states it reaches

coins(a):                                  dp[0] = 0
    if a == 0: return 0                    for a = 1 .. 15:
    if a in memo: return memo[a]               dp[a] = 1 + min(dp[a-c] for c ≤ a)
    memo[a] = 1 + min(coins(a-c) for c ≤ a)
    return memo[a]

The table computes every cell, needed or not. The recursion computes only what the answer reaches. With coins {4, 7} and amount 15, the calls go 15 → 11 → 7 → 3, then 0, 4, 8, 1: only amounts that are 15 minus some 4s and 7s. That is 8 states in 10 calls, one of them a memo hit (grey). The table fills all 16 cells, and the last step tints yellow the 8 it never needed: 2, 5, 6, 9, 10, 12, 13 and 14 (Demo: coin change). Both say 15 = 4 + 4 + 7, three coins.

This gap grows with sparse problems: large coins, game positions, or graph states you can't list in advance. A table has to cover every state that might be needed; the recursion pays only for the ones that are.

Bottom-up needs an order; top-down finds one

For the grid, paths(r, c) = paths(r − 1, c) + paths(r, c − 1). The loop must fill a cell only after the cell above and the cell to the left, so it goes row by row; a column-by-column order would work too, but filling right to left would read empty cells. The recursion never needs that decision: it calls whatever it needs and the call stack makes sure the inputs are done first. On this 3 × 4 grid the memo fills the inner cells in the same row-by-row order the loop uses (#1 to #6), and it skips one state, the corner (0, 0), which no path from (2, 3) asks for (Demo: grid paths).

The stack depth cost

Each open call is a stack frame; the column on the left of the canvas shows the frames open right now. Top-down needs a frame for every state on the current chain. For fib(n) the first chain goes n, n − 1, …, 1, so fib(12) holds 12 frames at once while the loop holds one (Demo: deep recursion fib(12)). For n = 5000 a memoized fib in Python stops with RecursionError (the default limit is 1000 frames), and in C or Java a deep enough chain overflows the stack. The table version has no such limit.

When both do the same work

On fib and on min-cost climbing stairs every state is needed, so both sides compute the same states in the same order; the only differences are the calls and the stack (Demo: min-cost stairs). Take the memo away, though, and the recursion rebuilds every repeated subtree (red): fib(6) makes 25 calls for 7 states, and fib(12) makes 465 instead of 23 (Demo: no memo). Plain Recursion vs Memoization vs Tabulation walks through that fib case in detail.

Side by side

Problem	Top-down calls (hits)	Top-down states	Max stack	Table cells	Answer
Coins {4, 7}, 15	10 (1)	8	4	16	3
Grid paths 3 × 4	13 (2)	11	5	12	10
fib(12)	23 (9)	13	12	13	144
Min-cost stairs	11 (3)	7	6	7	4
fib(6), no memo	25	7	6	7	8

Which one to use

• Top-down is the easiest to write from the recurrence (in Python, @functools.cache). It wins when the reachable states are a small part of the table, and when an order is hard to work out.
• Bottom-up has no recursion limit and no call overhead, and the fill order makes space savings easy: fib and stairs need only the last two cells, the grid only the previous row.
• Both do the same work per state. The difference is the order, the stack, and whether unneeded states are computed.

See also Plain Recursion vs Memoization vs Tabulation and Calculating nth Fibonacci number for the fib warm-up with code. For more tables: Making Change, Coin Change 0/1 Knapsack and Grid Paths.

What the page leaves out

The problems are kept small so the whole call tree fits; plain recursion on fib(12) is counted but not drawn. The page leaves out reconstructing the solution (which coins, which path), rolling the table down to one row or two variables, converting the recursion to an explicit stack, and the cost of hashing when the memo is a dictionary instead of an array.

References

Dynamic programming (Wikipedia)

Memoization (Wikipedia)

functools.cache (Python documentation)

sys.setrecursionlimit (Python documentation)