This lesson's interactive features are locked, please to keep using them
Memoization vs. Tabulation – Review
- Memoization: Top-down. We start with the big problem; solve subproblems as needed; and cache their results to avoid redundant work.
- Tabulation: Bottom-up. We start with the subproblems; solve them all; and use their results to build the solution to the big problem.
Should You Top-Down or Bottom-Up?
If the larger problem requires all of the subproblems to be solved, tabulation usually outperforms memoization by a constant factor. Tabulation has no overhead for recursion and can use a preallocated array rather than a hash map.
If only some of the subproblems need to be solved for the overall problem to be solved, then memoization is preferable because the subproblems are solved lazily. There's no need to compute subproblems that turn out to be irrelevant.