Overview
Both techniques avoid redundant recomputation in dynamic programming problems by caching subproblem results, but they build that cache in opposite directions. Memoization starts from the original problem and recurses downward, caching results lazily as calls return, while tabulation starts from the base cases and iterates upward, filling a table until the final answer is reached.
Comparison Diagram
Comparison Table
| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Entry point | Starts from the original problem call, e.g. solve(n) | Starts from the smallest base cases, e.g. dp[0], dp[1] |
| Control flow | Recursive function calls, following the natural recurrence | Iterative loop over subproblem indices in dependency order |
| Subproblems computed | Only those actually reachable from the initial call | All subproblems up to the target, whether needed or not |
| Storage structure | Hash map or sparse cache keyed by call arguments | Array or table indexed by subproblem parameters |
| Order dependency | Implicit, resolved automatically by call stack ordering | Explicit, programmer must sort iteration to respect dependencies |
| Call overhead | Function call and stack frame cost per subproblem | No function call overhead, just array reads and writes |
| Stack risk | Can hit recursion depth limits or stack overflow on deep inputs | No recursion, so no stack depth concerns |
| Code shape | Mirrors the recursive definition, often easier to derive first | Requires reformulating the recurrence as an explicit loop |
Key Differences
- Memoization computes subproblems on demand, while tabulation computes every subproblem exhaustively in order.
- Memoization relies on the call stack to sequence work; tabulation relies on a manually ordered loop.
- Tabulation typically enables space optimization (e.g. keeping only the last few rows) since access order is known upfront.
- Memoization can be stack-limited on deep recursion, whereas tabulation avoids recursion entirely.
- Memoization is usually a smaller code change from a naive recursive solution; tabulation requires restructuring it as iteration.
When to Use Each
Memoization (Top-Down)
- Sparse Subproblem Space: When only a subset of subproblems reachable from the initial call actually matters, memoization avoids computing the ones tabulation would fill in regardless.
- Quick Retrofit onto Recursive Code: Adding a cache to an existing recursive function is a smaller code change than restructuring the whole recurrence as an explicit loop.
- Recurrence Easiest to Express Recursively: When the natural recursive definition is simplest to derive first, memoization lets the call stack handle ordering automatically.
Tabulation (Bottom-Up)
- Deep or Large Inputs: Iterating in a loop instead of recursing avoids the stack overflow risk memoization faces on deep call chains.
- Memory-Constrained Environments: Since the iteration order is known upfront, tabulation enables space optimization, such as keeping only the last few rows instead of a full cache.
- Predictable, Overhead-Free Performance: Array reads and writes with no function-call or stack-frame cost make tabulation preferable when consistent execution cost matters.