Memoization vs Tabulation
Memoize first. It is the recursive solution plus a cache, so it is faster to write and harder to get wrong. Convert to tabulation when the recursion is too deep for the stack, or when you want to drop the table to a single row and save the memory.
These are two ways to write the same dynamic program, and they compute the same values. Memoization starts at the answer and recurses down to base cases, caching as it returns. Tabulation starts at the base cases and fills forward until it reaches the answer. The recurrence is identical either way, which is why the honest advice is to find the recurrence first and pick a direction second.
Side by side
| Dimension | Memoization | Tabulation |
|---|---|---|
| Direction | Top-down, from the answer | Bottom-up, from the base cases |
| Written as | Recursion plus a cache | Loops over an array |
| States computed | Only the reachable ones | All of them |
| Stack depth | O(depth), can overflow | None, it is iterative |
| Space optimisation | Hard, the cache is sparse | Easy, often to one or two rows |
| Order of evaluation | Handled by the recursion | You must get the loop order right |
| Debugging | Mirrors the recurrence | Requires reading the table |
When to pick each
Memoization
- You have just derived the recurrence and want a correct solution quickly.
- The state space is large but sparse, so most states are never reached. A memoized search touches only what it needs.
- The state is awkward to index, such as a string or a set, where a HashMap cache is easier than an array.
Tabulation
- The recursion would go deeper than the stack allows, which is common once n reaches the tens of thousands.
- You want to reduce the memory, since a table where each row depends only on the previous can collapse to one row.
- The constant factor matters, because iteration avoids the call overhead entirely.
Getting the loop order wrong when converting to tabulation. The recursion decided the evaluation order for you, and a bottom-up version has to reproduce it by hand. This is why 0/1 knapsack iterates capacity downward and unbounded knapsack iterates upward: the direction is what stops an item being reused within its own pass, and reversing it silently gives a wrong answer rather than an error.
Questions people ask
Is one faster?
Tabulation usually wins on constants because it avoids call overhead and its array access is sequential. Memoization can win outright when most states are unreachable, since it never computes them, and a full table does.
Which do interviewers prefer?
Neither, but they do want to see you derive the recurrence before writing either. Starting from a table without stating the state and the transition looks like a memorised solution rather than a derived one.
When can I drop the table to one row?
When each cell depends only on the previous row. That covers knapsack, edit distance and most grid problems. It does not cover anything reading two rows back or a distant column, so check the recurrence rather than assuming.