Every entry in this site's Dynamic Programming category
rests on the same guarantee: solve each distinct subproblem exactly once, then reuse the answer
every other time it's needed. Longest Common
Subsequence's own Why it works section states the guarantee and both ways to get it in the same
sentence: "filling the table bottom-up (or caching top-down recursion, 'memoization') means each of
the (m+1)(n+1) cells gets computed exactly once." Tabulation is the
first of those: a loop fills every cell, in a fixed order chosen so a cell's dependencies are always
already filled by the time it's reached, no recursion anywhere. Memoization is the
second: ordinary recursion, starting from whatever the real question asks for, with each answer
cached in a map the first time it's computed — the
Glossary's own entry calls it "the top-down way to get dynamic programming's 'solve each
subproblem once' guarantee without filling a table by hand." Same recurrence, same correctness
guarantee, same asymptotic worst case — this page is about where they genuinely differ.
Bottom-up tabulation fills every one of its cells, unconditionally, regardless of whether the
final answer actually needs each one. Top-down memoization starts at the one cell the real question
asks for and only recurses into a neighbor when the recurrence actually asks for it — so it can
finish having touched strictly fewer cells than the full table, when the input allows it.
Longest Common Subsequence's own Pitfalls section measured this directly rather than assuming it:
on its own 6×7 worked example, top-down "computes only 32 of the 56 possible cells (13 of those 32
lookups are cache hits reusing an already-computed neighbor, not new work) — 24 cells the bottom-up
table fills that this particular recursion never actually needed." The same section is honest that
this is a property of the input, not a guarantee: re-run the check against two strings sharing no
characters at all and "top-down touches 48 of the resulting 49 cells — every cell except
dp[0][0]," because a mismatch can't short-circuit the way a match does.
Edit Distance's own page measured the identical
experiment on its own, three-way recurrence, and found a smaller saving for a structural reason, not
a coincidence: "on this page's own 'kitten'/'sitting' example, top-down
computes 50 of the 56 possible cells (48 of those are cache hits) — nowhere near Longest Common
Subsequence's own 32-of-56 saving on a table the same size, because most cells here are mismatches
that still need all three neighbors" (substitute's diagonal, delete's up, insert's left, against
Longest Common Subsequence's two). The saving does show up where the structure allows it: two
identical 6-character strings "recurse along a single diagonal of matches and touch just 7 of 49
cells." The lesson both pages converge on: top-down memoization's savings track how often a match
lets the recursion short-circuit past its other branches — more branches per mismatch means less
room for that saving, and a sufficiently adversarial input (no shared characters at all) erases it
almost entirely, converging on the same cell count tabulation always pays.
Before weighing the two against each other, it's worth being clear neither is competing against
the real alternative: no caching at all. Longest Common Subsequence's own Pitfalls section states it
plainly — translate the recurrence into recursion with no memoization and "the call tree for two
length-n strings can reach O(2^n) calls, even though there are only
O(n²) distinct subproblems... the entire cost of the naive version is repeating
work that's already been done." Regular
Expression Matching's own Pitfalls section measured exactly how bad that repetition gets for a
non-DP recursion with the identical shape (every call fully determined by a pair of indices, no
caching): chaining twelve a* groups against a string of a's with no trailing match costs
7,904,455 calls at 12 a's and 82,317,689 at 16 — "a 10.4× jump from
adding just 4 more characters, not a fixed additive cost." That page's own Complexity section names
the fix without building it: "since every call is fully determined by the pair
(si, pi), and there are only (n+1)·(m+1) such pairs,
memoizing on that pair turns the same recursion into an O(n·m) dynamic-programming
table" — tabulation and memoization would both close this exact gap identically. Whichever one you
pick, picking either over nothing is the one decision that actually matters first.
Tabulation's loop keeps one stack frame alive for its entire run, no matter how large the table
gets. Memoization is ordinary recursion — every call still waiting on a nested one keeps its own
frame alive, exactly the resource How Deep Can You
Recurse? measures directly for three other reference implementations on this site. A memoized
recursion adds one more cost on top of that: a map lookup and a map write on every single frame, not
just the plain arithmetic a bare recursive call does. Press the button below to binary-search, live,
for how deep your own browser can recurse right now, both ways — plain recursion with no
cache at all, and the identical shape with a Map-backed memo bolted on.
Measured once in Node v20.20.2, for reference (your browser's own numbers from the demo above
will differ, the same way How Deep Can You
Recurse? found for its own two functions): plain recursion with no memo at all was safe to
15,699 and failed at 15,700 — close to the 12,800–15,656 band that
page measured for its own bare countdown, same shape, different run. The identical recursive chain
with a Map-backed memo bolted on — one extra has/get/set
per frame, nothing else changed — was safe only to 10,465, failing at
10,466: about a third shallower, from bookkeeping alone, before the memo has saved a
single recomputation. Tabulation's loop pays none of this, at any n, because it never
recurses at all.
That gap only tells the whole story for a one-dimensional recurrence, though — one
subproblem per index, like the chain above, or Weighted Interval Scheduling's
dp(i). A two-dimensional table like Edit Distance's or Longest Common
Subsequence's own dp[i][j] hits a different wall first. Instrumenting the exact
recurrence Edit Distance's own top-down mode uses (same evaluation order: diagonal neighbor first,
then up, then left) against two same-length strings sharing no characters at all — the worst case
established above, needing nearly the full table — confirmed live recursion depth grows only as fast
as the strings' own length, not as the table's cell count: depth 2,001 at length 2,000, matching
length 1 for 1. But the Map backing that memo needs one entry per cell, and
cell count grows as the square of the length: 4,004,001 entries at length 2,000, already approaching
V8's own documented hard limit on how large a single Map can grow,
2²⁴ ≈ 16.78 million entries. Pushing toward length ≈ 4,096 — depth only 4,097, nowhere
near the 10,465 the one-dimensional case above showed this same engine can hold — needs a memo
holding roughly that many cells and becomes impractically slow well before any stack concern, a
different resource hitting its ceiling first. For a table shaped like one sequence, depth is
the real risk; for a table shaped like two, the memo's own memory usually gets there first.
Reach for tabulation when the input is large enough that recursion depth or a
map's bookkeeping cost is a real concern, when the final answer genuinely needs most or all
subproblems anyway (erasing memoization's main advantage per the section above), or when the
space-optimization trick matters: Edit Distance's and Longest Common Subsequence's own
Complexity sections both note a two-row
version drops full O(m·n) storage to O(min(m,n)) — a saving that depends on
discarding old rows in a fixed order a loop controls, which a memoized version run for its
cache-reuse benefit can't do, since discarding an "old" entry is exactly what would break the next
cache lookup that needs it.
Reach for memoization when the state space is large but only sparsely reachable from the one real starting question — exactly the shape the section above shows pays off for Longest Common Subsequence on favorable input — or simply when the recursive formulation is the natural way to state the problem and a loop's fill order would have to be reverse-engineered from it by hand first. Either way, picking between them only matters once the floor above (no caching at all) is already off the table.
Assuming top-down memoization is inherently more space-efficient than bottom-up
tabulation. In the worst case it isn't: Longest Common Subsequence's own 48-of-49 and Edit
Distance's own 50-of-56 cell counts above show the memo can end up almost exactly as large as the
full table it was meant to avoid, and a Map entry generally costs more bytes per cell
than a plain array slot holding the identical number.
Assuming "fewer cells computed" and "less total work" are the same claim. They usually move together, but a cache hit still costs a lookup — Edit Distance's own count above includes 48 cache hits inside its 50 "computed" cells, each one real work that tabulation's direct array read does too, just without a hash step first.
Treating recursion depth as a theoretical concern that won't come up in practice. How Deep Can You Recurse?'s own Pitfalls section makes the general case: "the safe number is a property of the engine, not the language... treat any specific number quoted for it, including every number on this page, as a measurement taken in one engine at one moment, not a constant to hardcode into real code." The two numbers measured above are no different — a memoized recursion over tens of thousands of linear subproblems is a real, reachable size for a scheduling or sequence problem, not a contrived edge case.
O(n·m) memoized table its own recurrence would support
without building it.