Rolling array: keep only the last row of the DP table

The idea: a row only needs the row above

Many DP tables are filled row by row, and each cell reads only the row above and the row it is in. Once row i is done, row i − 1 is never read again, and nor is anything older. So the program does not need to keep them. Keeping only the rows still needed is called a rolling array: memory drops from O(n·m) to O(m), while the answer stays the same.

On the canvas the left panel is the full table as you would draw it on paper. The right panel is what the program really stores. Each memory box has a small tag such as [3][4]: the table cell it holds right now. When no box holds a cell any more, the cell fades: it has been dropped.

Two rows: prev and cur

The safe version keeps two arrays of length m + 1. prev holds row i − 1 and cur is filled with row i. After the row, the two names are swapped: no numbers are copied, the old prev array is simply reused and overwritten by the next row. This works for any rule that reads only rows i − 1 and i (Demo: LCS with two rows). An equivalent trick is to index the full table with i % 2.

for i in 1..n:
    cur[0] = base
    for j in 1..m:
        cur[j] = rule(prev[j-1], prev[j], cur[j-1])
    prev, cur = cur, prev          # swap the names
answer = prev[m]

One row: the loop order follows the arrows

With a single array, writing dp[j] destroys the old row's value in that slot. So at any moment the array is part new row, part old row, split at the cell being filled. A cell may read a slot only if it still holds the row it wants. That decides the direction of the loop:

problem	reads	one-row loop	wrong order gives
grid paths	up, left (new row)	j left to right: dp[j] += dp[j-1]	right to left adds the old diagonal
0/1 knapsack	up, up-left by w (old row)	c from W down to w	low to high: unbounded knapsack
LCS, edit distance	up, left, diagonal	left to right + one saved diag	diagonal read from the new row

For the knapsack, the "take the item" read dp[c − w] lies to the left and must come from the old row. Going from high c to low, those slots have not been written yet, so it works (Demo: knapsack one row, high to low, answer 45). Going low to high, dp[c − w] already includes the item, so the item is packed again and again: item 1 (weight 1, value 15) six times gives 90 (Demo: knapsack low to high reuses items). That wrong loop is exactly the right loop for the unbounded knapsack, where items may repeat; see Coin Change.

For grid paths, the left neighbour must be the new row, so the loop goes left to right and the whole update is dp[j] += dp[j−1]: 6 numbers instead of 24, and the 4 × 6 grid still has C(8, 3) = 56 paths (Demo: grid paths in one row). See Grid Paths for the full table.

LCS needs one more number: diag

LCS reads up, left and the diagonal dp[i−1][j−1]. Left to right, the left slot is new (good) and the up slot is old (good), but the diagonal sat in dp[j−1], which was just overwritten. The fix is to save it before overwriting:

for i in 1..n:
    diag = dp[0]
    for j in 1..m:
        tmp = dp[j]                      # dp[i-1][j], about to be lost
        dp[j] = diag + 1 if a[i] == b[j] else max(dp[j], dp[j-1])
        diag = tmp                       # becomes the diagonal of j + 1

That is m + 2 numbers for the 8 × 7 table: 8 instead of 56 (Demo: LCS with one row + diag). Forget diag and use dp[j−1] instead, and a matching letter is counted twice: for ABCBDAB and BDCAAB the answer comes out 5 instead of 4 (Demo: LCS one row without diag). The same pattern works for Edit Distance.

What you lose: the trace back

The rolling array keeps the value of the answer, not the table. To print the actual LCS letters or the chosen items you walk back from the answer cell through the table, and those rows are gone. Options: keep the full table when you need the solution, store only small "which choice" bits, or use Hirschberg's algorithm, which recovers an LCS in O(m) space by running the one-row DP forward and backward and splitting the problem in half.

layout	memory	LCS 8 × 7	trace back?
full table	(n + 1)(m + 1)	56	yes
two rows	2(m + 1)	14	no
one row (+ diag)	m + 1 (+ 1)	8	no

Time does not change: every layout fills all (n + 1)(m + 1) cells once. Also pick the shorter string or the smaller dimension as the row length, since the saving is O(min(n, m)). See also Longest Common Subsequence, 0/1 Knapsack and Memoization vs Tabulation: only bottom-up tabulation can roll its rows, because a memoized recursion may come back to any cell.

What the page leaves out

Hirschberg's algorithm itself; rolling over other dimensions (a 3-D DP keeping two layers, interval DP by length); bit-packing the choice table; tables whose rows read two or more rows back (keep k + 1 rows); and editing the strings or items (the page uses fixed samples).

References

Longest common subsequence: reducing the memory (Wikipedia)

Hirschberg's algorithm (Wikipedia)

0-1 knapsack problem (Wikipedia)

LeetCode 62: Unique Paths