DYNAMIC PROGRAMMING · CORE

DP space optimization

Keep only the rows or cells of a DP table that later cells still read, so memory shrinks from a whole table to one row or a few variables.

Time O(n × capacity)Space O(capacity)11 practice problemsStep-through picture

The idea

Many DP tables only look back a little. A grid DP cell reads the row above; a staircase cell reads the two cells before it. Every older row is never read again, so keeping it wastes memory.

Space optimization keeps just what is still needed: one or two rows instead of a whole grid, or two variables instead of an array. The answers are exactly the same; only the memory changes.

The template is the 0/1 knapsack with a single row. The trick is the loop direction: going from the largest capacity down to the smallest means each cell still reads the old row's values, so no item is used twice.

An everyday example

A whiteboard instead of a notebook

You can do long multiplication in a notebook, keeping every line forever. But each line only needs the line just above it, so you could use one small whiteboard: rub out the old line as you write the new one. The trick is to rub out each number only after you are done reading it.

How the example maps to the code
In the example	In the code
The whole notebook	A 2-D table with a row per item
The one whiteboard line	The single row `best`
Rubbing out and rewriting a number	`best[cap] = Math.max(...)`
Reading a number before it is rubbed out	Looping `cap` from `capacity` down

From the slow way to dp space optimization

Start with the full 0/1 knapsack table: n + 1 rows, one per item count, and capacity + 1 columns. For 1,000 items and a capacity of 100,000, that is about 100 million cells, roughly 800 MB as JavaScript numbers. The time is fine; the memory is not.
Look at what each row reads. Row i only reads row i - 1: the same column for skipping, and column cap - weight for taking. Rows 0 to i - 2 are never read again. So two rows are enough: the previous one and the one being filled. That brings the memory down to 2 × (capacity + 1) numbers.
Can one row work? Updating in place means some cells hold the new row while others still hold the old row. Each update reads its own column and a column to its left. If you go from the largest cap down to the smallest, everything to the left of cap is still untouched, so it still holds the old row's values, which is exactly what the rule needs.
So keep one array best of capacity + 1 cells, and for each item loop cap downward, stopping at the item's weight. Each pass turns the array from the old row into the new row in place. That backward loop is DP space optimization.

How it works

Look at the transition and list which earlier cells it reads.
If it reads only the previous row, keep one or two rows instead of the whole table.
Make best with capacity + 1 cells, all 0. Before any item, it is row 0 of the full table.
For each item i, update best in place to become the next row.
Loop cap from capacity down to weights[i], so best[cap - weights[i]] still holds the previous row's value when it is read.
Set best[cap] = Math.max(best[cap], best[cap - weights[i]] + values[i]), then return best[capacity].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function knapsackOneRow(weights, values, capacity) {
const best = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let cap = capacity; cap >= weights[i]; cap--) {
best[cap] = Math.max(best[cap], best[cap - weights[i]] + values[i]);
}
}
return best[capacity];
}

How fast it is

Time	`O(n × capacity)`
Extra memory	`O(capacity)`

The same number of cell updates as the 2-D table, but only one row of capacity + 1 numbers is kept.

Best caseO(n)
Every item is heavier than capacity: each pass stops at once, so only the outer loop runs.
Average caseO(n × capacity)
Any input: each item updates capacity - weight + 1 cells.
Worst caseO(n × capacity)
All items are very light, so every pass covers almost every cell. This is the same number of updates as the full table.

Common mistakes

Looping the capacity upward in the 0/1 knapsack, which quietly turns it into the unbounded knapsack.
Overwriting a value that a later cell in the same pass still needs, such as the diagonal in LCS. Save it in a variable first, or keep two rows.
Swapping rows by assigning prev = curr without making a new curr, so both names point to the same array.
Shrinking the table when the question also asks for the actual choices, which then can't be rebuilt.

When to use it

Look for these clues in a problem:

Each row of the table reads only the row right above it, or each cell only the last few cells.
The table would be too large for memory, such as 10^4 by 10^4 numbers.
Only the final value is needed, not the path or choices that produced it.
The question mentions a memory limit or asks for O(n) extra space.

Check yourself

Answer each one in your head first, then open it.

Why must cap go downward in the one-row 0/1 knapsack?

The take option reads best[cap - weight], a smaller index. Going downward means that cell hasn't been updated for this item yet, so it still holds the old row and the item is used at most once.

What does the upward loop compute instead?

The unbounded knapsack, where each item may be used any number of times. The smaller cell may already include the current item, so taking it again is allowed.

In the trace, why does cap = 6 for item 1 read 5 from best[4]?

best[4] hasn't been touched yet in item 1's pass, so it still holds item 0's row: item 0 alone, worth 5.

How much memory does the one-row version save for 200 items and capacity 10,000?

It keeps 10,001 numbers instead of 201 × 10,001 = 2,010,201, about 200 times fewer.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

#568Count Hidden Copies of a Keyword

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

During the pass for item i, the array keeps one promise: every cell above the current cap already holds the new row's value, and every cell at or below cap still holds the old row's value. Before the pass, every cell holds the old row, so the promise is true.

Each update keeps the promise. The rule for the new best[cap] needs the old best[cap] and the old best[cap - weight]. Both are at or below cap, so by the promise they still hold old values. After the update, best[cap] holds its new value and the loop moves down by one, so the promise still holds. Cells below weight never change, which matches the full table, where those cells copy the row above.

When the pass ends, the whole array equals row i of the full table. After the last item it equals the last row, and best[capacity] is the same answer as best[n][capacity]. The values match the 2-D table cell for cell; only the memory is different.

Going deeper

3 more ideas

Why the loop goes backwards

The 2-D rule reads best[i - 1][cap - weight], a smaller capacity in the previous row. If you loop upward in one row, best[cap - weight] has already been updated for this item, so taking the item again is possible. Looping downward updates large capacities first, while the small ones still hold the previous row.

Two rows when one is not enough

In LCS and edit distance, a cell reads the diagonal cell prev[j - 1] as well as the cell to its left in the new row. Keep two arrays, prev and curr, fill curr from prev, then swap them. For a 1-D DP that reads the last two cells, keep two variables and shift them each step.

What you give up

With the table gone, you can no longer walk back through it to list which items were chosen or which lines changed. If the question needs that list, keep the full table, or use a smarter method such as Hirschberg's algorithm, which rebuilds the path in linear space.

Work it by hand

Every step in a table, with why

Run the 0/1 knapsack in one row with 3 items and capacity 6. Each row of the trace is one update of best.

weights = [3, 2, 4], values = [5, 4, 7], capacity = 6

Step	`i`	`cap`	Old `best[cap]`	Take reads	New `best[cap]`	`best` after	What happens	Why
1	0	6	0	`best[3] = 0`	5	0, 0, 0, 0, 0, 0, 5	Take item 0	Item 0 weighs 3 and is worth 5. The row started as all zeros, which is row 0 of the full table.
2	0	5	0	`best[2] = 0`	5	0, 0, 0, 0, 0, 5, 5	Take item 0	Going down: each read is to the left, in the part not yet updated.
3	0	4	0	`best[1] = 0`	5	0, 0, 0, 0, 5, 5, 5	Take item 0	Same again for bag size 4.
4	0	3	0	`best[0] = 0`	5	0, 0, 0, 5, 5, 5, 5	Last size that fits	The loop stops at `cap = 3`, the item's weight. Sizes 0 to 2 keep the old row's 0.
5	1	6	5	`best[4] = 5`	9	0, 0, 0, 5, 5, 5, 9	Take both items	`best[4]` still holds item 0's row, so this is "item 0, then item 1": `5 + 4 = 9`.
6	1	5	5	`best[3] = 5`	9	0, 0, 0, 5, 5, 9, 9	Take both items	Weights 3 and 2 fit exactly in 5.
7	1	4	5	`best[2] = 0`	5	0, 0, 0, 5, 5, 9, 9	Skip wins	Taking item 1 alone gives 4, less than the 5 already there.
8	1	3	5	`best[1] = 0`	5	0, 0, 0, 5, 5, 9, 9	Skip wins	Again, item 0 alone is better.
9	1	2	0	`best[0] = 0`	4	0, 0, 4, 5, 5, 9, 9	Take item 1	Bag size 2 now holds item 1. The pass for item 1 is done.
10	2	6	9	`best[2] = 4`	11	0, 0, 4, 5, 5, 9, 11	Take items 1 and 2	`best[2]` is item 1 from the last pass, so `4 + 7 = 11` uses weights 2 and 4.
11	2	5	9	`best[1] = 0`	9	0, 0, 4, 5, 5, 9, 11	Skip wins	Item 2 alone gives 7, less than 9.
12	2	4	5	`best[0] = 0`	7	0, 0, 4, 5, 7, 9, 11	Take item 2	The loop stops at `cap = 4`. Line 8 returns `best[6]`.

It returns 11, the same as the full table. Looping cap upward instead returns 12, because item 1 gets taken three times (4 + 4 + 4), which the 0/1 rule forbids.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
DP space optimization	`O(n × capacity)`	`O(capacity)`	You only need the final value and the full table would be too big.
Full 2-D table	`O(n × capacity)`	`O(n × capacity)`	You need to rebuild which items were chosen, or you're still debugging the transition.
Two rows	`O(n × capacity)`	`O(capacity)`	The transition reads the new row as well as the old one, so a single row can't keep both, as in LCS.
Memoization	`O(n × capacity)`	`O(n × capacity)`	Only a small part of the states is reachable. It can't easily drop old states, so it saves no memory.

Extra memory: O(capacity): one row of capacity + 1 numbers, instead of (n + 1) × (capacity + 1).

How the steps grow

DP space optimization, Full 2-D table, Two rows, Memoization O(n × capacity)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
DP space optimization	100	1 million	1 trillion
Full 2-D table	100	1 million	1 trillion
Two rows	100	1 million	1 trillion
Memoization	100	1 million	1 trillion

Inputs that need care

5 tricky inputs

An item heavier than the bag: The loop condition cap >= weights[i] is false at once, so the pass does nothing. That matches the full table, where its row is a copy.
An item of weight 0: best[cap - 0] is best[cap] itself, read before the write, so each cell adds the value once. That is still the 0/1 rule, since each cell is updated only once per pass.
capacity = 0: best has one cell. Only weight-0 items have a pass, and the answer is the sum of their values, or 0.
The loop direction flipped to upward: Each update would read cells already updated for the same item, so items get reused. For this trace's input it returns 12 instead of 11, which is the unbounded knapsack's answer.
The question also asks which items were chosen: The one row can't be walked back. Keep a separate table of true or false choices (much smaller as bits), or keep the full table.

Variations and follow-ups

Twists interviewers add

Two rows for LCS and edit distance

Those cells read the diagonal prev[j - 1] and the new cell to the left, curr[j - 1]. Keep prev and curr, fill curr from prev, then swap them. One row also works if you save the old diagonal value in a variable before overwriting it.

Two variables for 1-D tables

When a cell reads only the last two cells, as in the staircase or the no-neighbors problem, keep prev and prevPrev and shift them each step. The space drops to O(1).

Rolling rows with `i % 2`

Allocate two rows and write row i into rows[i % 2], reading row i - 1 from rows[(i - 1) % 2]. The code looks like the full-table version, which makes it easy to get right.

Rebuilding the answer in little memory

Hirschberg's method finds the actual LCS or edit script in O(n) space. It runs the two-row DP forward on one half and backward on the other, finds where the best path crosses the middle row, and recurses on the two sides.

In an interview

Spot it, explain it, answer follow-ups

Bring it up after a working table solution: "each row only reads the row above, so I can keep one row". Interviewers often ask for this as the follow-up to any 2-D DP.
Before shrinking, list exactly which cells the transition reads. If it reads only the old row, one row may be enough. If it reads the new row too, check the loop direction or keep two rows.
Test the loop direction with one item that could fit twice, such as weight 2 in a bag of 4: the right answer uses it once. Going upward wrongly returns twice its value.
Expect "what do you lose?". You can no longer walk back through the table to list the chosen items or the edits, so mention the extra choice table or Hirschberg's method.

Where frontend code uses it

The same idea in real UI code

Diffing two large files in the browser can use a lot of memory with a full LCS table; diff libraries use methods that keep much less, such as Myers' linear-space variant.
On mobile devices with limited memory, keeping one row instead of a table is the difference between a smooth page and a crashed tab.
Running totals in charts, such as a moving best value, keep a couple of variables instead of an array of every past value.

DP space optimization

The idea

An everyday example

A whiteboard instead of a notebook

From the slow way to dp space optimization

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why the loop goes backwards

Two rows when one is not enough

What you give up

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Two rows for LCS and edit distance

Two variables for 1-D tables

Rolling rows with `i % 2`

Rebuilding the answer in little memory

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

A whiteboard instead of a notebook

From the slow way to dp space optimization

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why the loop goes backwards

Two rows when one is not enough

What you give up

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Two rows for LCS and edit distance

Two variables for 1-D tables

Rolling rows with i % 2

Rebuilding the answer in little memory

In an interview

Where frontend code uses it

Related algorithms

Rolling rows with `i % 2`