A DP over crates must report the chosen set, not just the optimum — how do you budget memory for that?

## Why reconstruction and compression pull against each other A DP fill answers "what is the best achievable value?" Reconstruction answers "which decisions achieved it?" — and that second question is answered by reading the table backwards: at the final cell, compare against the cells the recurrence could have come from, decide which predecessor was used, step there, repeat. Every one of those reads is on a row that a rolled implementation has already discarded. That is the whole tension, and it is a real constraint, not a shortcoming of anyone's implementation: the compressed run genuinely does not contain the information any more. You cannot recover it from the surviving row, because the last row records only what was achievable, never how. ## The options, priced **Keep the full table.** Space equal to the number of states, reconstruction is a straightforward backward walk, and the code stays legible enough to debug by printing. For a picker over a few thousand crates and a bounded capacity, the table is a handful of megabytes and this is simply the correct answer. Refusing it because compression is available is optimizing a resource nobody is short of. **Store one decision bit per cell.** The reconstruction walk usually needs far less than the cell's value; often it only needs "was this crate taken here?" Storing a bit instead of a numeric cell keeps the same cell count but shrinks the constant by roughly an order of magnitude or two. That converts many tables that were several times over budget into ones that fit, while leaving the algorithm and the walk-back essentially unchanged. It does not change the asymptotics, so it buys you one scale step, not the next one. **Divide and conquer over the midpoint.** The classic linear-space reconstruction — Hirschberg's scheme — runs the fill forward over one half and backward over the other, both in rolled form, determines where the optimal path crosses the middle, and recurses on the two resulting subproblems. Space drops to linear in one dimension; the recomputation adds up to a geometric series, so the total work is roughly twice the plain fill. It is the genuinely clever option, and it is also the one a future maintainer is least likely to understand, which is a cost that belongs in the decision. **Bound the input.** If the product can say "a pick list covers at most N crates", the table is bounded by construction and none of the above is needed. This is often the cheapest fix available and the one engineers reach for last, because it lives in the product conversation rather than in the code. **Re-solving repeatedly** deserves a mention only to be rejected: pinning one decision and re-running the DP for the rest recovers the choices without extra storage, but at a factor of n more work. It is the option that sounds free and is not. | Option | Extra space | Extra time | Maintenance cost | |---|---|---|---| | Full table | states × cell width | none | lowest | | Decision bit per cell | states × 1 bit | none | low | | Divide and conquer | linear in one dimension | about 2× | high | | Repeated re-solving | none | about n× | medium | | Bounded input | none | none | product change | ## Making the call The decision is not "which is most efficient" but "which resource is actually scarce, and at what input size". Price the table at the real p99 input, not the theoretical maximum — a picker whose realistic worst case is a few thousand crates has no memory problem to solve. If the table genuinely does not fit, try the decision-bit form first, because it preserves the shape of the code. Reach for divide-and-conquer only when the constant-factor win is not enough and the input cannot be bounded, and when you reach for it, pay the associated costs deliberately: a written explanation of why it is there, a reference implementation to test against, and an owner who understands it. The argument to a reviewer pushing on the memory line is made with numbers, not principle: here is the table size at the real input distribution, here is the added running time and the code complexity of the alternative, and here is the fact that listing the chosen crates *is* the feature — the memory exists to deliver it. Equally, if the numbers say the table is 40 GB, no amount of "but the feature needs it" makes the plain table shippable, and the conversation moves to bounding the input. ## What a weak answer sounds like "Roll it, then reconstruct from the last row" — the information is not there. "Parent pointers are basically free" — a pointer per state is usually larger than the value it accompanies. "Always use the linear-space scheme, it is strictly better" — it is strictly better on one axis and worse on two others.