Memoization vs Tabulation Visualization | Top-down vs bottom-up DP

The idea: one problem, three ways

The Fibonacci numbers are defined by fib(0) = 0, fib(1) = 1 and fib(k) = fib(k − 1) + fib(k − 2). The canvas computes fib(n) three times. Plain recursion turns the definition straight into code. Top-down memoization keeps that code but remembers every answer in a cache. Bottom-up tabulation drops the recursion and fills a table with a loop, smallest index first. All three give the same answer; they differ in how much work they do.

Left: the plain call tree of fib(5) with 15 circles; the second fib(3) subtree and every repeated fib(2), fib(1) and fib(0) are red, 9 of 15 calls. Right: the memoized tree of fib(5) with 9 circles; the second fib(3) and fib(2) are green cache hits with no children — Plain recursion builds the same subtrees again (red). With a cache, the second call to fib(3) or fib(2) is a lookup (green) and its subtree is never built.

Plain recursion: overlapping subproblems

fib(k):
    if k < 2: return k
    return fib(k-1) + fib(k-2)

Each call makes two more, so the calls form a binary tree. fib(6) makes 25 calls, but there are only 7 different arguments (0 to 6): 18 calls redo work that was already done. That is what overlapping subproblems means. The number of calls is 2·fib(n + 1) − 1, so it grows by about φ ≈ 1.6 for each step of n: 9, 15, 25, 41 calls for n = 4 to 7, and over a billion for n = 45 (Demo: plain recursion fib(6), Demo: fib(7)).

Top-down memoization: cache the answers

memo(k):
    if k < 2: return k
    if k in cache: return cache[k]      # cache hit
    cache[k] = memo(k-1) + memo(k-2)
    return cache[k]

The recursion still starts at the top, fib(n), and dives down the left side to fib(1). On the way back up each answer is stored. When fib(k − 2) is asked next, it is already in the cache: a cache hit, returned at once with no further calls. Each cache entry is computed exactly once, so fib(n) takes 2n − 1 calls: 11 for fib(6), with 3 hits (Demo: memoization fib(6)). The stack still gets n calls deep, which is why a memoized fib(100000) in Python hits the recursion limit.

Bottom-up tabulation: fill the table in order

dp[0] = 0; dp[1] = 1
for i in 2..n:
    dp[i] = dp[i-1] + dp[i-2]

Here you choose the order yourself: every cell depends only on cells to its left, so a left-to-right loop always finds its inputs ready. There are no calls at all, just n − 1 additions (Demo: tabulation fib(6)). Watch the order numbers under the cache and under dp: the memo filled cache[2], cache[3], … in the very same order. Top-down reaches the same cells through a stack of calls; bottom-up reaches them with a loop.

The dp array 0, 1, 1, 2, 3, 5, 8 with arrows from dp[3] and dp[2] into dp[4]; below, the two-variable version where the pair (a, b) slides from (0,1) to (8,13) — Each cell reads the two cells just before it, so the table can shrink to two variables.

Because only the last two cells are ever read, the table can be replaced by two variables: O(1) space. Tabulation makes such savings easy to spot; the same trick keeps only one row of an LCS or knapsack table.

Side by side

	Plain recursion	Memoization (top-down)	Tabulation (bottom-up)
Calls for fib(6)	25	11 (3 hits)	0 (5 additions)
Time	O(φⁿ)	O(n)	O(n)
Extra space	O(n) stack	O(n) cache + O(n) stack	O(n) table, or O(1)
Who picks the order	the recursion	the recursion	you
Solves	every call, again and again	only the subproblems it reaches	every cell in the table

Which one to use

Memoization is the easy first step: write the recursion, add a cache (in Python, @functools.cache). It wins when only a few subproblems are actually needed, for example some coin-change amounts or game states.
Tabulation avoids deep recursion and function-call overhead, and makes space savings visible. It needs an order in which every cell's inputs come first.
Either way, the problem must have optimal substructure (the answer is built from answers to smaller subproblems) and overlapping subproblems; otherwise caching saves nothing.

See also Calculating nth Fibonacci number (the three versions with their code), Making Change and Longest Common Subsequence for the same three approaches on harder problems, and Greedy vs DP Coin Change.

To keep deep recursion from overflowing the stack, see Tail Call Optimization.

What the page leaves out

The canvas stops at fib(7) so the whole plain call tree fits. It leaves out problems where top-down solves fewer subproblems than the full table, 2-D tables (grid paths, LCS, edit distance), recovering the solution by tracing back, the closed-form and matrix-power O(log n) ways to get fib(n), big-integer cost for large n, and tail-call or iterative rewrites of the recursion.