Two routes to the same answers
Once a problem has optimal substructure and overlapping subproblems, dynamic programming can be coded in two styles. Memoization is top down: keep the natural recursion but cache each result. Tabulation is bottom up: fill a table of subproblem answers in dependency order with explicit loops.
How they differ
Both compute every distinct subproblem exactly once, so they share the same asymptotic running time, but they feel different in practice.
- Memoization follows the recursive structure, so it only computes subproblems actually reached, but it carries recursion call overhead and risks stack overflow on deep inputs.
- Tabulation computes the table in a fixed order, often computing every cell even if some are unneeded, but it avoids recursion overhead and can sometimes shrink memory by keeping only recent rows.
Choosing between them
Reach for memoization when the recursion is natural and only a sparse part of the state space is visited. Reach for tabulation when you need tight control over memory or want to eliminate deep recursion. They are interchangeable in correctness.
Key idea
Memoization caches results within natural recursion top down, while tabulation fills a table bottom up; both compute each subproblem once but trade recursion overhead against table control.