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.
The 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
Tiny 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 this kind of problem
- 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.