Why This Matters
Memoization and tabulation solve many of the same dynamic programming problems, but they shape the code differently. The right choice depends on state reachability, recursion depth, and fill order.
Decision Rule
Use memoization when the recursive definition is clear and only some states may be reached. Use tabulation when you know the dependency order and want iterative control over memory and stack usage.
Comparison Table
| Feature | Memoization | Tabulation |
|---|---|---|
| Direction | top-down | bottom-up |
| Control flow | recursion plus cache | loops over table |
| Computes unreachable states | often avoids them | often fills all planned states |
| Stack risk | recursion depth | no recursion stack |
| Common fit | tree-shaped choices, sparse states | grid DP, sequence DP, memory optimization |
Worked Example
For Fibonacci, memoization starts with fib(n) and recursively asks for fib(n-1) and fib(n-2), caching answers.
Tabulation starts with fib(0) and fib(1), then fills fib(2), fib(3), up to fib(n).
Both remove repeated exponential work. They differ in direction and implementation shape.
Common Mistakes
| Mistake | Correction |
|---|---|
| Thinking memoization and DP are separate topics. | Memoization is a top-down DP technique. |
| Forgetting base cases in memoized recursion. | The cache does not replace the recurrence definition. |
| Filling tabulation states before dependencies exist. | Bottom-up DP needs a valid dependency order. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which style uses recursion? | Memoization. |
| Which style is usually easier to memory-optimize with rolling arrays? | Tabulation. |
| Why can memoization be better for sparse state spaces? | It computes only states reached by recursive calls. |
Exercises
- Beginner: Write memoized Fibonacci in Python.
- Beginner: Write tabulated Fibonacci in Python.
- Beginner: Explain why naive recursive Fibonacci repeats work.
- Intermediate: Convert a memoized grid-path recurrence to a table.
- Intermediate: Identify a valid fill order for edit distance.
- Challenge: Optimize a tabulated 2D DP to one row and explain the dependency condition.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/