The same table, filled two ways

There are two ways to fill a table, and every account of dynamic programming presents them as a matter of taste. Write the recursion and hang a cache off it, or write the loops and fill the cells in an order that works. Same recurrence, same answers, same asymptotic cost — pick whichever reads better.

Measured on two four-hundred-character strings, they agree on more than that. Both compute exactly 160,801 cells. Both consider the same transitions. Both return 217.

They differ in two numbers neither of them is usually asked for. The recursion makes 480,001 calls, asks the table 480,001 questions, and at its deepest holds 401 stack frames. The loops make no calls, ask no questions, and hold none.

And on a different problem the cell counts stop agreeing entirely: on a knapsack with fourteen items and a capacity of 3,200, the recursion fills 2,157 cells and the loops fill 48,015.

The order is not in the recurrence #

A recurrence states what a cell depends on. It says nothing whatever about when to compute it, and this is worth being precise about because the difference between the two strategies is entirely a difference of order.

Cell $(i, j)$ needs $(i-1, j-1)$, $(i-1, j)$ and $(i, j-1)$. Any order in which those three are complete before $(i, j)$ is attempted is a valid order. Row by row is one. Column by column is another. Anti-diagonal by anti-diagonal is a third, and it is the one the rest of this field needs: on the $d$-th anti-diagonal every cell depends only on cells of diagonals $d-1$ and $d-2$, which is what makes a band walkable and what would make the fill parallel.

There is a fourth valid order that is worth naming because it is the one nobody writes and everybody relies on: any topological order of the dependency graph. The three above are convenient special cases, and the reason there are exactly three convenient ones is that the dependency arrows all point up and to the left, so anything that sweeps up-and-leftwards to down-and-rightwards works. A recurrence whose arrows pointed in four directions would have no row order at all, and the usual way to notice that is to write the loops, get an answer, and never find out it is wrong.

A top-down recursion is a fifth order, and it is the only one that is not written down anywhere. It is whatever order the recursion happens to reach the cells in, which for this recurrence is a depth-first walk from the far corner: the diagonal predecessor first, so the recursion drives to the top-left corner immediately and then unwinds. Nobody chose that order. It is a consequence of the argument order in a min, and swapping two arguments changes it entirely while changing nothing else about the computation — same cells, same answer, different sequence.

That is a small thing and it has one large consequence. Because the order is not stated, it cannot be relied on, so nothing downstream of a top-down fill may assume anything about when a cell was computed. Every technique in the rest of this field assumes exactly that.

What the recursion pays for choosing its own order #

The price is on the stack, and this site has measured what that costs before.

A top-down fill of an $n \times m$ table recurses to a depth that grows with $n$: 401 frames on four-hundred-character strings, and it is the diagonal chain from the corner to the origin that sets it. A bottom-up fill recurses to a depth of zero, because it is two loops.

That is not an accounting curiosity. The stack nobody counts measured quicksort on sorted input taking one frame per element and exhausting a real engine’s stack somewhere past seven thousand of them. A memoised edit distance over two strings of ten thousand characters wants ten thousand frames and will not get them in most runtimes. The table would fit — a hundred million cells is large but finite — and the recursion is what fails, on a problem whose bottom-up form has no stack at all.

What the loops pay for having their order chosen in advance #

The loops fill every cell of the rectangle. They have no way not to: the order is fixed before the run begins, so a cell is filled because it is in the rectangle rather than because anything needs it.

On edit distance that costs nothing, because every cell of the rectangle is reachable — some optimal or near-optimal alignment passes through every one of them. On a recurrence whose subproblems are sparse it costs a great deal.

The knapsack is the standard case and it is stark. A table indexed by item and remaining capacity has $(n+1)(W+1)$ cells. But the capacities a recursion can actually reach are the ones some subset of the weights leaves behind — $W$ itself, $W$ minus each weight, $W$ minus each pair, and so on down. With fourteen items whose weights sum to 437, no capacity below $W - 437$ is reachable at all, and most of those above it are not either.

The weights here are 7, 29, 10, 14, 60, 59, 39, 14, 60, 46, 36, 3, 1 and 59. Their sum is 437, so a recursion starting at capacity 3,200 can never see a capacity below 2,763, and the rectangle’s first 2,763 columns are filled by the loops for no reason at all.

The top-down column stops moving at 2,157. It is not converging on anything, and it is not a sampling artefact: past a capacity of 437 the items cannot consume the difference, so raising $W$ adds cells to the rectangle and adds nothing to the set of reachable subproblems. The bottom-up table’s size is set by a number in the input; the top-down one’s is set by the items.

That gap is the honest version of a claim usually made loosely. “Top-down only computes what it needs” is true, it is the reason top-down is worth having, and the size of the effect is a property of the recurrence rather than of the strategy: on edit distance it is zero, and on this knapsack it is a factor of twenty-two.

The freedom is not a property of one pair of strings either. The same three orders run on a pair whose answer is not the textbook three, and the gate requires all three tables to agree cell for cell there too.

The probe, and what it measures #

The counter this field uses charges probes for a memoised recursion’s question — is this subproblem already answered? — and hits for the ones that find something. A bottom-up fill has neither, because it never asks: it reads cells by index, knowing they are there.

On the four-hundred-character pair the recursion asks 480,001 questions and 319,200 of them are answered from the table. That ratio, 66.5%, is a measurement of how much sharing the recurrence has, and it is the number the phrase overlapping subproblems refers to. A recurrence with no overlap would report zero hits and the memo would be pure overhead; a recurrence with heavy overlap reports a hit rate approaching one, and there the table is the whole algorithm.

The hit rate also moves with the shape of the input in a way the cell count does not. On the knapsack above the recursion asks 3,479 questions and 1,322 of them are answered from the table — a hit rate of 38%, against edit distance’s 66.5% — and the reason is structural rather than statistical: an edit-distance cell has three predecessors and is therefore reached from three directions, and a knapsack cell has two. A recurrence’s hit rate is bounded by how many arrows point at a cell, and measuring it is the cheapest way to find out whether a memo is worth attaching at all.

It is worth noting what the probe is not. It is not a cache miss and it is not a comparison. This site counts those elsewhere and both are properties of a machine or of a data type; a probe is a property of the strategy, it exists in the top-down version and not in the bottom-up one, and no amount of hardware makes it go away.

The one thing they cannot disagree about #

There is a check worth stating because it is what makes every comparison above a comparison of two computations rather than of two programs.

The two strategies must agree on the values in every cell, not merely on the answer at the corner. That is a stronger requirement and it is the one this site’s gate makes: three bottom-up orders and a top-down recursion are run over the same pair, and the resulting tables are compared cell for cell. A run that agreed at the corner and differed in the interior would be a run whose recurrence had been quietly altered — a boundary condition off by one, say — in a way that happened to cancel.

That check costs nothing and it has a general form: when two implementations of one recurrence are being compared on cost, compare their whole state and not their output. The output is a single number and a single number is a weak test. The table is the thing both of them claim to have computed, and it is available.

What the table refuses #

The bottom-up strategy has one failure mode that the top-down strategy structurally cannot have, and it is the reason this site’s table throws.

If the loops run in the wrong order — the outer one counting down where it should count up, which is a single character — then a cell is computed before the cells it depends on. Against a plain zero-filled array that reads as a distance of zero, and a zero is absorbed silently into a minimum. The result is an answer that is a plausible small integer, a table full of plausible small integers, and a smooth curve across any sweep of sizes anybody cares to run.

DpTable.get on a cell that has not been written throws instead, and the gate asks for a reversed fill and requires the refusal. The message names the diagnosis rather than the symptom, because the diagnosis is the useful half: the recurrence is right and the evaluation order is wrong.

A top-down recursion cannot make that mistake. It computes a cell’s dependencies by calling for them, so the order is derived from the recurrence rather than restated beside it, and that is the strongest argument for the top-down form that this field found — stronger than the sparsity argument, because it is about correctness rather than cost.

The hybrid nobody writes #

The knapsack comparison sets up a genuine dilemma — the recursion computes a twenty-second of the cells and pays four hundred stack frames for the privilege — and there is a third strategy that takes both halves. It is not exotic and it is not in any account of dynamic programming this collection is aware of.

Compute the reachable set first, then loop over it. For the knapsack the reachable capacities are $W$ minus the subset sums of the weights, and that set is computed by a bitset of $W+1$ bits shifted and or-ed once per item — fourteen shifts of a 3,201-bit word here, which is nothing. Then run the ordinary loops, skipping every column not in the set.

The result has the recursion’s cell count and the loops’ stack depth: 2,157 cells and no frames. It also keeps the loops’ other advantage, since the cells are still visited in a known order and a row can still be released when the next is complete — which the recursion cannot do at all.

What it costs is a preliminary pass and a set to hold, and both are cheap precisely when the gap is large. The reachable set is small exactly when the rectangle is mostly unreachable, which is the case where the hybrid is worth building; where every cell is reachable, as in edit distance, the pass finds everything and the hybrid degenerates to the plain loops with no loss but the pass.

So the four-way comparison below is a comparison of two strategies that both leave something on the table, and the reason nobody writes the third is probably that the reachability pass looks like extra work — which it is, by a factor that is dwarfed by what it saves whenever it saves anything.

A fifth thing separates them, and it is not a number #

The list below has four entries because the fifth is not a quantity, and it is worth stating first because it decides more than the other four on a large enough problem.

A bottom-up fill can be run in parallel and a top-down one cannot. In anti-diagonal order every cell on a diagonal depends only on the two diagonals before it, so all the cells of one diagonal are independent and can be computed at once — the fill becomes $n + m$ sequential steps of up to $\min(n,m)$ parallel work each. That is a real speedup available on a real machine, and it is available because the order was written down.

A top-down recursion’s order is whatever the argument order in a min produces, it is not stated anywhere, and nothing can be run concurrently without knowing which cells are independent. Memoising a recursion across threads additionally needs the table to be safe against two threads computing the same cell at once — which is correct if they compute the same value, and is a great deal of coordination for a computation whose sequential form has none.

The same property decides whether the fill can be streamed. Row order needs one row of the first string in hand and one character of the second, so the second string can arrive incrementally; a recursion needs both strings before it starts, because it begins at the far corner.

Both consequences come from the same source, and it is the one the essay opened with: an order that is written down is an order that other things can be built on. The recursion’s order is derived rather than declared, which is what makes it correct by construction and what makes it useless to everything downstream.

Which to use, stated as measurements rather than as advice #

Four things separate them and all four are numbers this field can produce.

Frames. Top-down takes $\Theta(n)$ of them and bottom-up takes none. Above roughly ten thousand this decides the question outright.

Unreachable cells. Bottom-up fills the rectangle. Where the rectangle is much larger than the reachable set — a capacity, a large state space with few live states — the gap is a factor rather than a constant, and it grows with the parameter that is not a length.

What can be released. Bottom-up in row order permits releasing each row when the next is complete, which takes the space from $\Theta(nm)$ to $\Theta(m)$; that is the next essay. Top-down cannot release anything, because it does not know which cells it will ask for again. This is the exact opposite of the previous point and it is why neither strategy wins.

Probes. Top-down pays one per arrival at a subproblem, and two thirds of them are answered from the table. Bottom-up pays none.

Two of those favour the recursion and two favour the loops, and which pair matters is decided by the recurrence rather than by preference. That is the useful form of the answer, and it is available only because the two strategies were measured on quantities the usual comparison does not have — a table that could not report frames, probes and reachable cells separately would have to conclude that they are the same thing written differently.

The last thing worth saying is about what a textbook is doing when it presents the choice as a matter of style. It is not being careless: on the problem those presentations use — a single sequence, a full rectangle, a modest size — the two really are interchangeable, and every quantity that separates them is zero or small. The distinction only appears once one of the parameters stops being a length: a capacity, a bit budget, a state space with an unreachable interior. That is the same shape as every other result on this site where a bound turned out to be a statement about a particular regime, and the useful habit is the same one — find the parameter the bound is silent about, then move it and measure.