memoization vs tabulation

Memoization (top-down) and tabulation (bottom-up) are two ways to implement the very same dynamic program — the same states, the same transition, the same base cases, the same final answer. They differ only in how the table gets filled. Top-down writes a recursive function with a cache and lets the recursion decide what to compute and when; bottom-up writes loops that fill the table in a fixed order you choose. Picking between them is an engineering decision, not a correctness one: a correct recurrence yields the same answers either way.

To convert top-down to bottom-up, you make the implicit dependency order explicit. In the memoized version, solve(state) recurses into the states it depends on, so the call order is some valid topological order of the dependency graph 'state X needs state Y'. Tabulation just hard-codes a loop order that respects that same graph — typically increasing index when bigger states depend on smaller ones. Going the other way is just as direct: take the loops, drop the explicit order, and let recursion plus a cache rediscover it. Because both realize the identical recurrence, they have the same asymptotic running time, (states) times (work per transition).

When to prefer which? Top-down shines when only a sparse subset of states is actually reachable (it skips the rest for free), when the natural recursive structure is much easier to write than a hand-derived loop order, or when the evaluation order is awkward to state. Bottom-up shines when you need maximum speed (no call overhead), when recursion would overflow the stack for large n, and especially when you want to shrink memory by keeping only a sliding window of recently filled cells — a rolling-array trick that top-down cannot easily do because it may revisit old states at any time.