Algorithms / Dp Memo Vs Tabulation
Least You Need to Know: Memoization vs Tabulation
Memoization and tabulation solve the same recurrence in different directions. Interview questions often ask when one is simpler, when one avoids wasted work, and how iteration order reflects dependencies.
Least you need to know
- Memoization is top-down: recurse on demand and cache solved states.
- Tabulation is bottom-up: fill states in an order that guarantees dependencies are already known.
- If only a small fraction of states are ever reached, memoization can avoid useless work.
- Tabulation avoids recursion-depth concerns and can have lower constant overhead.
- Both approaches should agree on the same state definition and recurrence.
Key notation
- cache[state] — memoized value for a solved subproblem
- table[i] — bottom-up DP entry already filled
- dependency order — an ordering where prerequisite states appear earlier
Worked example
- Fibonacci can be solved top-down with a memoized recursive function or bottom-up with an array.
- Both use the same recurrence
F(n)=F(n-1)+F(n-2). - The difference is whether states are requested on demand or filled in dependency order.
Common mistakes
- Students often think memoization and tabulation solve different problems instead of the same recurrence.
- Students often write a bottom-up loop in an order that reads values not filled yet.
- Students often ignore recursion-depth or constant-factor tradeoffs.
How to recognize it
- Ask whether all states will be needed or only a sparse subset.
- Ask whether recursion depth could become a practical issue.
- For tabulation, write arrows from each state to its dependencies and fill in a valid order.
Next recommended lesson
Continue through this topic with Least You Need to Know: Dynamic Programming Mixed Interview Drills.
Least You Need to Know: Dynamic Programming Mixed Interview DrillsRelated lessons
Keep going with nearby lessons in the same topic.