When only a fraction of a DP's table cells are reachable, does memoization or tabulation win?
answer
- declared cells versus cells anyone asks for
- which form gets to skip work
- the recursion is doing a reachability walk
- overhead is a constant, waste is a factor
- count distinct states computed, then compare
basics
~20 sMemoization wins on a sparse state space: it computes only states actually reached from the goal, while a table pays time and memory for every declared cell. A scheduling DP with ten million cells but ten thousand reachable states is three orders of magnitude of wasted work for the table.
solid answer
~50 sTop-down does work proportional to the *reachable* states; bottom-up does work proportional to the *declared* state space. When a scheduling recurrence has coordinates whose ranges multiply to around ten million cells but the transitions only ever land on about ten thousand combinations, the table spends nearly all of its time and its whole allocation on cells nobody reads. Memoization discovers the reachable subgraph for free — that is what the recursion is doing. The counterweights are real, though: per-state call and cache-probe overhead, scattered memory access, keyed storage instead of dense indexing, and recursion depth. So the rule is a ratio, not a slogan. If the reachable fraction is small, top-down; if it is near total and the transition is cheap, the table's tighter constant factor wins. When it matters, instrument the memoized run, count distinct states computed, and compare that with the product of the coordinate ranges.
go deeper
Know that a table computes every cell you declare, while a memoized recursion only computes what something asks for — so an enormous, mostly unused state space favours the recursive form.
Explain both sides of the ratio: reachable versus declared state counts on one hand, per-call overhead and memory locality on the other, and say which dominates at which fraction.
Show you would measure — distinct states computed versus the product of the coordinate ranges, plus allocation size — and that you know reachability depends on the input data, not just the recurrence.
Own the call under real constraints: a memory ceiling on a shared worker, a latency budget, and a team that must keep the chosen form correct as the state space grows.
## Declared states versus reachable states When you write a DP you declare a state space by giving each coordinate a range: shifts 0..N, hours remaining 0..H, staffing level 0..S. The product of those ranges is the table's size. But the recurrence does not usually connect all of them. Transitions move by data-dependent amounts — shift lengths, gaps between bookable slots, discrete staffing steps — so starting from the goal state only a subset of the coordinate combinations is ever asked about. Call that subset the **reachable states**. A scheduling DP whose declared table is around 10^7 cells can easily have only ~10^4 reachable ones when the transitions step by realistic shift durations. Three orders of magnitude separate the two numbers, and which one you pay for is decided entirely by the implementation form: - **Top-down memoization** evaluates a state only when something asks for it. Its work is `reachable states x transition cost`. The recursion *is* the reachability traversal; you get the pruning for free without writing a line for it. - **Bottom-up tabulation** iterates the declared ranges. Its work is `declared states x transition cost`, plus the cost of allocating and touching the whole table. On that scheduling shape, the table does roughly 1000x the useful work and reserves memory proportional to the full product, while the memoized run touches ten thousand entries. This is the single strongest argument for top-down, and it is one many candidates never reach for. ## The counterweights, stated honestly Sparse reachability is not a blanket verdict, because top-down pays for its flexibility per state: - **Per-state overhead.** A call plus a cache probe, versus a loop increment and an indexed write. When the transition itself is a couple of comparisons, this overhead is a meaningful multiple, not a rounding error. - **Memory locality.** A dense table is walked in order and prefetches beautifully; a keyed cache is chased in discovery order. On large dense problems this alone can decide the benchmark. - **Storage shape.** Sparse states need a keyed cache with per-entry overhead; dense states index straight into a flat table with none. - **Depth.** Recursion depth tracks the longest dependency chain, which on a long horizon is a separate constraint you must check before choosing top-down. So the decision is a ratio. Roughly: if the reachable fraction is small — well under half, and certainly at 0.1% — top-down does less real work and the overhead cannot make up a factor of a thousand. If the fraction is near total and the transition is cheap, the table's tighter inner loop wins, and it wins by a constant factor you can actually measure. ## Measuring rather than arguing The measurement is cheap and settles the question. Instrument the memoized version to count **distinct states computed**, then compare with the product of the declared coordinate ranges. That single ratio tells you what a table would waste. Add a second number — bytes the table would allocate — because a large declared space can be a memory verdict before it is a time verdict: tens of millions of cells is a serious allocation to hand a worker process that is also serving traffic. Be careful about generalising from one input. Reachability is a property of the *data*, not of the recurrence: a scheduling instance with uniform shift lengths may reach far more states than one with three distinct durations. Measure across representative inputs, including the pathological ones, before hard-coding a choice. ## Can bottom-up be made sparse? Yes, and it is worth knowing the shape of it. Enumerate the reachable states first with a traversal from the goal, then fill them in topological order of the induced subgraph. You get the iterative form's stack safety and the sparse work profile together. You also get: a two-pass algorithm, an explicit sort, keyed storage anyway, and enough machinery that you have essentially rebuilt memoization with extra steps. It pays off in exactly one situation — you need the explicit order for something else, such as reclaiming table memory or a depth constraint you cannot violate — and otherwise it is complexity for its own sake. ## The claim this question exists to break "Tabulation is always better because recursion is slow." It is a constant-factor argument applied to a case where the *amount of work* differs by orders of magnitude, and constants do not recover a thousandfold gap. The useful version of the claim is narrower and true: on a dense state space with a cheap transition, the iterative form's lower per-state overhead and better locality make it the faster of two implementations that do the same work. Say that version, and say what you would measure to know which case you are in.
- How would you measure which form wins instead of arguing about it?Instrument the memoized run to count distinct states computed, and compare that with the product of the declared coordinate ranges — the ratio is exactly what a table would waste. Add the bytes the table would allocate, since a large declared space can be a memory verdict before it is a time one. Repeat across representative inputs; reachability is a property of the data.
- Can a bottom-up fill be made to skip unreachable states too?Yes: traverse from the goal to enumerate reachable states, then fill them in topological order of that subgraph. You keep stack safety and gain the sparse work profile, at the cost of two passes, an explicit sort, and keyed storage — which is memoization with extra machinery. Worth it only when you need the explicit order for something else.
- Does a small reachable fraction always mean top-down is faster in wall-clock terms?Not always, but the gap has to be small for the overhead to matter. Per-call and cache-probe costs are a constant multiple, typically a few times the cost of an indexed write. At a reachable fraction of a few percent, no constant recovers that; near total reachability, the same constant is exactly what makes the table win.
saying these in an interview costs you the question
- Says tabulation is always better because recursion is slow
- Ignores that a table allocates every declared cell
- Claims both forms always compute the same set of states
- Treats call overhead as able to outweigh a thousandfold work gap
- Never proposes measuring the reachable fraction