Converting a memoized recursion to a bottom-up table: how do you derive the fill order?
answer
- look at what each state reads
- the table moves toward the goal, recursion moves away
- base cases become seeded cells
- dependencies must be final before the write
- wrong order reads sentinels and stays silent
basics
~20 sRead off which states each recursive call depends on, then fill the table in any order where every dependency is already final when a cell is written — usually the reverse of the direction the recursion moves. Base cases become cells seeded before the loop.
solid answer
~50 sThe conversion is mechanical once you look at the dependency direction. For each state, list the states its recurrence reads; the table must be filled in a topological order of that dependency graph, which for most DPs collapses to a simple loop direction. If the recursion for state `d` calls smaller `d`, fill ascending; if it calls larger `d`, fill descending; if it reads a previous row, iterate rows outward from the seeded one. The recursion's base cases become the cells you write before the loop starts, and its early-return guards become the loop bounds. The failure mode is nasty: an order that violates a dependency does not crash — it reads a cell still holding its initial sentinel and quietly produces a wrong answer, often only for some inputs. Cross-check the table against the memoized version on random small inputs.
code
pseudocode · 10 lines// cost[d] = cheapest way to license exactly d seats
// bundle k covers seats[k] seats for price[k], reusable
cost[0] = 0
for d in 1..D:
cost[d] = INFINITY
for k in 0..K-1:
if seats[k] <= d and cost[d - seats[k]] != INFINITY:
cost[d] = min(cost[d], price[k] + cost[d - seats[k]])
...
// answer for the whole order: cost[D]go deeper
Know that a table has to be filled in an order where the cells it reads are already computed, and that this order usually runs opposite to the direction the recursion travels.
Be ready to do the conversion live: state each cell's dependency set, choose the loop direction per coordinate, place the base cases, and say precisely what goes wrong with the reverse order.
Demonstrate the safety net — differential testing against the memoized version, a sentinel that cannot be a real answer, and an assertion that catches an order violation instead of shipping a quietly wrong table.
Weigh the conversion as a change with risk: it buys stack safety and memory tricks, and costs a correctness argument. Decide when a working top-down path is left alone and what evidence justifies touching it.
## The conversion is a question about dependency direction A memoized recursion hides its evaluation order inside the call graph. To make it iterative you must surface that order and prove it. The procedure has four steps, and none of them require you to re-derive the recurrence. **1. Write down the dependency set.** For each state, list exactly the states the recurrence reads. In the seat-licensing example above, `cost[d]` reads `cost[d - seats[k]]` for every bundle size `k` — always a strictly smaller index, because a bundle covers at least one seat. **2. Find a topological order of the dependency graph.** Any order where each state comes after everything it reads is valid. Most DPs never need an actual topological sort, because the dependency direction is monotone in some coordinate: strictly smaller index means ascending, strictly larger means descending, "previous row" means row by row outward from the seeded row. When the state has several coordinates, each may impose its own direction, and you nest the loops accordingly. **3. Seed the base cases.** The recursion's terminating branches become the cells written before the main loop. `cost[0] = 0` is exactly the `if d == 0: return 0` branch, relocated. Anything the recursion treated as impossible becomes the initial sentinel — here `INFINITY`, chosen because no real licensing cost can equal it. **4. Turn the guards into bounds.** A recursive early return like `if i >= n: return 0` becomes the loop's range and a base cell; a `if seats[k] > d: skip` guard stays as an inner test because it depends on data, not on the loop variable alone. ## What breaks when the order is wrong Suppose you iterate `d` from `D` down to `1` in the fragment above. Nothing crashes. Every index is in range, every read is legal — but `cost[d - seats[k]]` has not been computed yet, so it still holds `INFINITY`. The guard then rejects every candidate and `cost[d]` stays `INFINITY` for all `d` except the seeded zero. The whole table is empty and the answer is "impossible", for an order that is trivially satisfiable. That is the mild version. The dangerous version is a sentinel that is also a plausible answer — a cost table initialised to `0`, a length table initialised to `0`, a boolean table initialised to `false`. Then a wrong fill order does not produce an obviously broken table; it produces a table that is *slightly* wrong, on some inputs only, and the bug ships. This is why the conversion deserves an explicit ordering argument rather than "it worked on the sample". ## Reading the direction off a recursion, in general - The recursion computes state `s` from states "closer to the base case". Bottom-up must therefore move **from** the base cases **toward** `s`. If the recursion counts down, the table counts up, and vice versa. This reversal is the single sentence worth memorising. - Multi-dimensional states: derive a direction per coordinate, then check that the nesting respects all of them simultaneously. A cell that reads `(i-1, j)` and `(i, j-1)` is happy with any nesting of two ascending loops; a cell that reads `(i-1, j)` and `(i, j+1)` needs `i` ascending and `j` descending. - Not every DP has a nested-loop order. When states form an arbitrary graph — transitions that jump to data-dependent states with no monotone coordinate — you either run a real topological sort over the reachable states first, or you keep the top-down form, which never needed an order in the first place. "Keep it memoized" is a legitimate engineering answer here, not a cop-out. ## Verifying the conversion The conversion is exactly the kind of change that looks obviously right and is not. Two cheap checks: - **Differential testing.** Keep the memoized version and assert both produce the same answer on many random small inputs. Comparing whole tables, not just the goal cell, localises the first divergent state and usually points straight at the offending loop direction. - **Sentinel discipline.** Assert that no cell is read while still holding the sentinel, at least in a debug build. That assertion turns a silent wrong answer into a loud failure at the exact cell where the order is violated. ## Why bother converting at all The iterative form buys you no stack depth, lower per-state overhead, sequential memory access, and — the reason that most often forces the conversion — an explicit, known fill order, which is the precondition for keeping only a slice of the table in memory. What it costs you is the ordering argument, which is the entire content of this question.
- What if the states form a graph with no natural loop direction?Then either enumerate the reachable states and topologically sort them before filling, or keep the memoized version. Some DPs over arbitrary state graphs have no monotone coordinate to iterate on, and forcing a nested loop means inventing an order you cannot justify. Top-down is the honest choice there, with stack depth as the thing to watch.
- How would you verify the converted table matches the recursion?Run both on many random small inputs and compare, ideally whole tables rather than only the final answer, so the first divergent state names the broken loop direction. Add a debug assertion that no cell is read while still holding its sentinel; that turns an order violation into an immediate failure instead of a subtly wrong result.
- Do the base cases always become cells, or can they stay as conditions?Usually cells written before the loop, which keeps the loop body uniform. A base case that depends on data rather than position sometimes stays as a test inside the loop. Either is fine as long as the cell is final before anything reads it; what is not fine is leaving it to the loop to compute a state that has no recurrence.
saying these in an interview costs you the question
- Says any fill order works because each cell is written once
- Expects a crash when the fill order is wrong
- Cannot explain where the base cases go in the iterative form
- Initialises a cost table to a value that is also a valid answer
- Believes every DP has a nested-loop iteration order