Saving memory: from a table to a few variables

A DP table often holds far more than it needs. If each cell only reads the last row (or the last one or two cells), every older row is dead weight once the next one is done. Keep only what the recurrence still reads, and an O(n · k) table becomes O(k) — or an O(n) array becomes two variables. Same answer, same time, a fraction of the memory.

Two ways to save memory. Top: Fibonacci only reads the two previous values, so two variables slide along instead of an array of n + 1. Bottom: Pascal's rule only reads the row above, so one row is updated in place. It must be updated from right to left: updating row[2] reads the old row[1], which would already be overwritten if row[1] were updated first.

1D: keep the last few values

When dp[i] reads only dp[i−1] and dp[i−2], the array can shrink to two variables that slide forward:

1function fib(n) {2  if (n === 0) return 0;3  let prev = 0, cur = 1;                 // dp[i - 2] and dp[i - 1]4  for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];5  return cur;6}

JavaScript6 lines

2D: keep one row, and mind the direction

Pascal's rule reads dp[i−1][j−1] and dp[i−1][j] — only the previous row. Keep a single row and update it in place: row[j] += row[j − 1]. The catch is the direction: row[j] needs the old row[j − 1]. Going right to left, row[j − 1] hasn't been updated yet when row[j] reads it. Going left to right would read a value from the new row and get the wrong answer.

Dry-run simulator

C(n, k) with one row

One row is updated from right to left, so every cell still reads the previous row's values.

1function binomial(n, k) {2  const row = new Array(k + 1).fill(0);3  row[0] = 1;                                         // row 0: C(0, 0) = 14  for (let i = 1; i <= n; i++) {5    for (let j = Math.min(i, k); j >= 1; j--) {       // right to left: row[j - 1] is still the old row6      row[j] += row[j - 1];7    }8  }9  return row[k];10}

JavaScript10 lines

Time O(n · k), space O(k). The same right-to-left rule shows up in the 0/1 knapsack (each item used once) — and the opposite, left to right, in the unbounded knapsack (items reused), where reading the new row is exactly what you want. Both appear in Pattern 3.

Full table: O(n · k) time, O(n · k) space. One row: O(n · k) time, O(k) space.

The rules for shrinking a table

Look at what the recurrence reads. If row i reads only row i − 1, keep two rows or one. If dp[i] reads dp[i − 1] and dp[i − 2], keep two variables.
Two rows are always safe: prev and cur, swapped after each row. One row needs the right update direction.
When one row isn't enough: if a cell reads both the old row and the new row (edit distance reads up, left and diagonal), keep one row plus one saved variable for the old diagonal.
When not to shrink: if you must rebuild the actual solution (the path, the items chosen), you need the full table to walk back through.

Key takeaways

Memory only needs to hold what the recurrence still reads.
1D → a few variables; 2D → one or two rows: O(n · m) becomes O(m).
Updating one row in place: right to left when each item is used once, left to right when it may be reused.
Keep the full table if you need to reconstruct the answer, not just its value.

Prev Next

Was this helpful?

Saving memory: from a table to a few variables

1D: keep the last few values

2D: keep one row, and mind the direction

The rules for shrinking a table

Key takeaways

Keep exploring