Why can a bottom-up DP that fills a 2D table often keep only two rows in memory?
answer
- look at what the right-hand side reads
- which rows can never be read again
- memory holds live values, not history
- the recurrence sets its own look-back depth
- reads row i-1 only means two rows live
basics
~20 sOnly the cells that a pending transition still reads have to stay in memory. When every value in row i is computed from row i-1 alone, the finished earlier rows are dead weight, so two rows are enough.
solid answer
~50 sThe table is a record of everything computed, but memory only has to hold what is still *live* — the cells some not-yet-computed state will read. If the recurrence writes row `i` using nothing but row `i-1`, then the moment row `i` is finished, row `i-1` can never be read again and row `i-2` was already useless. So you allocate two buffers, fill one from the other, and swap them each outer step; some people index the single 2D buffer by `i mod 2` instead. The window size falls straight out of the recurrence: if the transition also reached back to row `i-2`, you would keep three. Nothing about the answer or the number of computed states changes — only the storage. What you give up is the table itself, and with it anything that needed to look back at it.
code
pseudocode · 10 lines// best[i][c] = best value from the first i crates within weight limit c
for i in 1..n
for c in 0..C
best[i][c] = best[i-1][c]
if weight[i] <= c
cand = best[i-1][c - weight[i]] + value[i]
if cand > best[i][c]
best[i][c] = cand
...
answer = best[n][C]go deeper
Be ready to point at the right-hand side of a recurrence and say which rows it reads. If it reads only the row directly behind, say so and conclude that two buffers are enough.
Explain the mechanics out loud: two buffers swapped by reference each outer step, or one buffer indexed by the parity of the outer loop. Derive the number of resident rows from the recurrence's look-back depth rather than reciting 'two'.
Show judgment about when not to compress. Name what the table was still buying you — reconstruction, later queries, debuggability — and be clear that relieving memory does nothing for a job that is also too slow.
Own the convention. Decide whether a fleet-wide memory ceiling justifies compressed code the team must maintain and debug, and make that a stated default rather than a per-author preference.
## The table is a log; memory only needs the live set A bottom-up DP fills a grid of subproblem answers. Each cell is a state, and the recurrence says which already-computed cells its value is built from. It is tempting to think the whole grid must exist because "DP stores subproblems" — but storing a subproblem is only useful while something still intends to read it. The right question is never "how many cells does this DP have?" but "at the moment I compute cell X, which cells can still be read by X or by anything after it?" That set is the live set, and it is all the memory the computation actually requires. ## The dependency window Read the right-hand side of the transition and note the largest row offset it reaches back to. ``` for i in 1..n for c in 0..C best[i][c] = best[i-1][c] if weight[i] <= c cand = best[i-1][c - weight[i]] + value[i] if cand > best[i][c] best[i][c] = cand ``` Every read here is `best[i-1][...]`. The deepest offset is 1, so at any instant only the row being written and the row directly behind it can be touched again. Two buffers suffice. | Deepest row offset the transition reads | Rows that must stay resident | |---|---| | i-1 only | 2 | | i-1 and i-2 | 3 | | a fixed k rows back | k+1 | | arbitrary earlier rows (unbounded look-back) | all of them — no compression | That last line matters: rolling is not a universal trick applied to "any DP". It is a consequence of a bounded look-back, and a recurrence whose transition may consult any earlier row cannot be rolled at all. ## Mechanics Two idioms are common. Keep two separate buffers, `prev` and `cur`, fill `cur` from `prev`, then swap the two references at the end of the outer step — swapping references, never copying contents, because copying a row costs as much as computing it. Or keep one buffer of two rows and address it by the parity of the outer index, so `table[i mod 2]` is the row being written and `table[(i-1) mod 2]` is the row behind it. Both are the same idea; the parity form avoids the swap, the two-buffer form reads more plainly. ## What changes and what does not Nothing about the computation changes. The same states are visited, the same transitions are evaluated, the same optimum comes out. Time complexity is untouched — this is a memory optimization, full stop. The one honest performance side effect is a constant-factor one: a working set of two rows is far friendlier to a memory hierarchy than a grid that no longer fits in cache, so rolled versions are often somewhat faster in wall-clock terms even though the asymptotics are identical. Never sell that as a complexity improvement. What you lose is real. The finished rows are gone, so anything that wanted to look at them is gone with them. You cannot walk backwards through the table to see which choice each state made; you cannot answer a second, different query afterwards without re-running the fill; and you cannot print the grid while debugging a wrong answer, which is the single most effective way to debug a DP. For a table small enough to fit comfortably, keeping it is a legitimate choice and the compression buys nothing. ## Going further than two rows Many DPs whose transition reads only row `i-1` can be squeezed further, down to a single array, because the row being written and the row behind it can share storage. That step is not free the way the two-row step is: once the two rows are superimposed, the order in which you sweep the row decides whether a read sees the old value or the freshly written one, and getting that order wrong changes the recurrence rather than merely slowing it down. Treat the two-row form as the safe default and the one-array form as a deliberate move with a stated invariant. ## The wrong answers to avoid "Rolling makes it faster" — no, it makes it fit. "Every DP can be reduced to two rows" — only those with a one-row look-back. "We compress, so we compute fewer states" — the state count is set by the recurrence, not by where you put the results.
- Does keeping two rows instead of the whole table change the running time?No. The same states are computed and the same transitions evaluated, so the asymptotic time is identical. The only realistic effect is on constants: a two-row working set fits a memory hierarchy far better than a grid that has spilled out of cache, so the rolled version is often modestly faster in wall-clock terms. That is a constant-factor win, never a complexity win.
- What if the transition also read row i-2?Then you keep three rows. The number of resident rows is one more than the deepest row offset the recurrence reaches back to — that is the whole rule. A transition with a fixed k-row look-back needs k+1 buffers; a transition that may consult any earlier row has an unbounded look-back and cannot be rolled at all.
- What do you actually give up by discarding the finished rows?Anything that needed to read them: walking back through the table to recover which choice each state made, answering a different query afterwards without re-running the fill, and printing the grid while debugging. If the table fits in memory comfortably, keeping it is a perfectly defensible choice — the compression is only worth its costs when the table genuinely does not fit.
A conveyor belt of assembly steps: each station only reaches back to the tray behind it, so you keep two trays and recycle the rest rather than lining up the whole day's output.
saying these in an interview costs you the question
- Says compressing rows lowers the time complexity too
- Claims any DP can be reduced to two rows
- Ignores what the transition actually reads
- Copies the row instead of swapping the two buffers
- Assumes rolling changes the computed answer, not just storage