23.06Intermediate4 topics16 min4 interactive animations

DP optimization basics

Reducing the space of a dynamic programming table: rolling arrays, one-row compression, state elimination and why the 0/1 choice needs reverse iteration.

Learning goals

Keep only the rows of a table that later rows need
Compress a two-dimensional table into one row without corrupting it
Eliminate a state dimension that the others imply
Explain why the 0/1 knapsack loop runs backwards and the unbounded loop forwards

Prerequisites

Bottom-up tabulationCanonical beginner DP

A table of a million by a million cells will not fit in memory, but if each row depends only on the previous one, you never needed the whole table.

23.06.1

Rolling arrays

When row i depends only on row i - 1, keep two rows and swap them: a **rolling array**. The longest common subsequence table compares prefixes of two strings, and each row needs only the row above it, so the O(m · n) table shrinks to two rows of n + 1 cells. If a row depends on the k previous rows, keep k + 1 rows and index them modulo k + 1.

The price: you can no longer reconstruct the answer by tracing back through the table, since the old rows are gone. Use the full table when you need the solution itself and the rolling version when only the value matters. The climbing-stairs animation with its “two variables” preset is the one-dimensional version of the same idea.

Java

1static int lcsLength(String a, String b) {
2    int n = b.length();
3    int[] prev = new int[n + 1], cur = new int[n + 1];       // two rows instead of an (m + 1) x (n + 1) table
4    for (int i = 1; i <= a.length(); i++) {
5        for (int j = 1; j <= n; j++) {
6            cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
7        }
8        int[] t = prev; prev = cur; cur = t;                 // the finished row becomes the previous row
9    }
10    return prev[n];
11}

Best

O(mn)

Average

O(mn)

Worst

O(mn)

Space

O(n)

Climbing stairs: a table, then two variables

Interactive · edit the input

dp[i] = ways to reach step i

1i=0

1i=1

?i=2

?i=3

?i=4

?i=5

?i=6

?i=7

Setup

To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.

Step 1 / 8

Java

1static long ways(int n) {                         // dp[i] = number of ways to reach step i with moves of 1 or 2
2    long[] dp = new long[n + 1]; dp[0] = 1;       // one way to stand at the start: do nothing
3    if (n >= 1) dp[1] = 1;
4    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];   // arrive from i-1 or from i-2
5    return dp[n];
6}
7static long waysRolling(int n) {
8    long prev2 = 1, prev1 = 1;                    // dp[0], dp[1]
9    for (int i = 2; i <= n; i++) { long cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }   // forget what is no longer needed
10    return prev1;
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=7	To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.
2	L4	i=2 dp[i-1]=1 dp[i-2]=1 dp[i]=2	dp[2] = dp[1] + dp[0] = 1 + 1 = 2.
3	L4	i=3 dp[i-1]=2 dp[i-2]=1 dp[i]=3	dp[3] = dp[2] + dp[1] = 2 + 1 = 3.
4	L4	i=4 dp[i-1]=3 dp[i-2]=2 dp[i]=5	dp[4] = dp[3] + dp[2] = 3 + 2 = 5.
5	L4	i=5 dp[i-1]=5 dp[i-2]=3 dp[i]=8	dp[5] = dp[4] + dp[3] = 5 + 3 = 8.
6	L4	i=6 dp[i-1]=8 dp[i-2]=5 dp[i]=13	dp[6] = dp[5] + dp[4] = 8 + 5 = 13.
7	L4	i=7 dp[i-1]=13 dp[i-2]=8 dp[i]=21	dp[7] = dp[6] + dp[5] = 13 + 8 = 21.
8	L5	return=21	21 ways to climb 7 stairs. Time O(n); space O(n). This is the Fibonacci recurrence.

23.06.2

One-row compression

Sometimes one row is enough: update the single row **in place**, as long as every read still sees the values from the previous row. In the 0/1 knapsack, dp[w] after processing item i should equal the old dp[w] or the old dp[w - weight] + value; with one array the old values of smaller w must still be there when dp[w] is computed.

The “1D backwards (correct)” preset runs the single-row version on items 1:15, 3:20, 4:30 with capacity 4 and gets 35, the same value as the full table, using 5 cells instead of 20.

Java

1static int knapsack1D(int[][] items, int capacity) {
2    int[] dp = new int[capacity + 1];            // dp[w]: best value within capacity w using the items seen so far
3    for (int[] item : items) {
4        int weight = item[0], value = item[1];
5        for (int w = capacity; w >= weight; w--) {           // backwards: dp[w - weight] still holds the previous item's row
6            dp[w] = Math.max(dp[w], dp[w - weight] + value);
7        }
8    }
9    return dp[capacity];
10}

Best

O(nW)

Average

O(nW)

Worst

O(nW)

Space

O(W)

0/1 knapsack: 2D table, and why 1D must run backwards

Interactive · edit the input

grid · 5 × 6

012345

item \ cap

none

#1 (1:15)

#2 (3:20)

#3 (4:30)

Cell being computedCell it readsOn the tracebackWrong: item reused

Setup

dp[i][c] is the best value from the first i items with capacity c. Row 0 is all zeros. Each cell either skips item i (copy the cell above) or takes it (value + the cell above-left by the item's weight).

Step 1 / 17

Java

1static int knapsack2D(int[] w, int[] v, int cap) {
2    int n = w.length; int[][] dp = new int[n + 1][cap + 1];            // dp[i][c]: best value from the first i items with capacity c
3    for (int i = 1; i <= n; i++)
4        for (int c = 0; c <= cap; c++) {
5            dp[i][c] = dp[i - 1][c];                                    // skip item i
6            if (c >= w[i - 1]) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // or take it
7        }
8    return dp[n][cap];
9}
10static int knapsack1D(int[] w, int[] v, int cap, boolean backwards) {
11    int[] dp = new int[cap + 1];
12    for (int i = 0; i < w.length; i++) {
13        if (backwards) for (int c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // right to left: dp[c - w] still excludes item i
14        else           for (int c = w[i]; c <= cap; c++) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // left to right: item i may be taken again (a bug for 0/1)
15    }
16    return dp[cap];
17}

Live state

items

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	items=3 capacity=4	dp[i][c] is the best value from the first i items with capacity c. Row 0 is all zeros. Each cell either skips item i (copy the cell above) or takes it (value + the cell above-left by the item's weight).
2	L6	item=1 c=0 skip=0 take=does not fit dp[i][c]=0	Item 1 (weight 1) does not fit in capacity 0: copy the cell above (0).
3	L6	item=1 c=1 skip=0 take=15 dp[i][c]=15	Capacity 1: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
4	L6	item=1 c=2 skip=0 take=15 dp[i][c]=15	Capacity 2: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
5	L6	item=1 c=3 skip=0 take=15 dp[i][c]=15	Capacity 3: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
6	L6	item=1 c=4 skip=0 take=15 dp[i][c]=15	Capacity 4: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
7	L6	item=2 c=0 skip=0 take=does not fit dp[i][c]=0	Item 2 (weight 3) does not fit in capacity 0: copy the cell above (0).
8	L6	item=2 c=1 skip=15 take=does not fit dp[i][c]=15	Item 2 (weight 3) does not fit in capacity 1: copy the cell above (15).
9	L6	item=2 c=2 skip=15 take=does not fit dp[i][c]=15	Item 2 (weight 3) does not fit in capacity 2: copy the cell above (15).
10	L6	item=2 c=3 skip=15 take=20 dp[i][c]=20	Capacity 3: skip item 2 → 15; take it → 0 + 20 = 20. Keep 20.
11	L6	item=2 c=4 skip=15 take=35 dp[i][c]=35	Capacity 4: skip item 2 → 15; take it → 15 + 20 = 35. Keep 35.
12	L6	item=3 c=0 skip=0 take=does not fit dp[i][c]=0	Item 3 (weight 4) does not fit in capacity 0: copy the cell above (0).
13	L6	item=3 c=1 skip=15 take=does not fit dp[i][c]=15	Item 3 (weight 4) does not fit in capacity 1: copy the cell above (15).
14	L6	item=3 c=2 skip=15 take=does not fit dp[i][c]=15	Item 3 (weight 4) does not fit in capacity 2: copy the cell above (15).
15	L6	item=3 c=3 skip=20 take=does not fit dp[i][c]=20	Item 3 (weight 4) does not fit in capacity 3: copy the cell above (20).
16	L6	item=3 c=4 skip=35 take=30 dp[i][c]=35	Capacity 4: skip item 3 → 35; take it → 0 + 30 = 30. Keep 35.
17	L8	return=35 items=[#1, #2]	Best value 35. Traceback from the bottom-right cell: whenever a cell differs from the one above it, that item was taken (items [#1, #2]), and we move left by its weight.

23.06.3

State elimination

Sometimes a state has a dimension that other dimensions already determine, or one that only ever takes a couple of values. Replace it by a handful of variables. House robber's flag 'was the previous house robbed?' can be kept as two arrays, take[i] and skip[i], with take[i] = skip[i - 1] + value[i] and skip[i] = max(take[i - 1], skip[i - 1]). Each only depends on the previous index, so the two arrays become two variables.

A second kind of elimination is a quantity fixed by the others: if the state is (items used, total weight, total count) and total count is determined by the items used, drop it. Before dropping a dimension, check that no transition reads it.

Java

1// two-state version of house robber, with the 'previous robbed' flag as two variables
2static int robTwoState(int[] value) {
3    int take = Integer.MIN_VALUE / 2, skip = 0;              // best totals where the last house was robbed / skipped
4    for (int v : value) {
5        int newTake = skip + v;
6        int newSkip = Math.max(take, skip);
7        take = newTake;
8        skip = newSkip;
9    }
10    return Math.max(take, skip);
11}

House robber: take it or skip it

Interactive · edit the input

house money

2h1

7h2

9h3

3h4

1h5

dp[i] = best from the first i houses

0none

2rob h1

?i=2

?i=3

?i=4

?i=5

Setup

For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).

Step 1 / 6

Java

1static int rob(int[] a) {                             // no two adjacent houses
2    int n = a.length; int[] dp = new int[n + 1];      // dp[i] = best loot from the first i houses
3    dp[1] = a[0];
4    for (int i = 2; i <= n; i++)
5        dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);   // skip house i, or rob it and use the best before the neighbour
6    return dp[n];
7}

Live state

houses

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L3	houses=5	For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).
2	L5	i=2 skip=2 rob=7 dp[i]=7	House 2: skipping keeps 2; robbing gives dp[0] + 7 = 7. Best 7 (rob it).
3	L5	i=3 skip=7 rob=11 dp[i]=11	House 3: skipping keeps 7; robbing gives dp[1] + 9 = 11. Best 11 (rob it).
4	L5	i=4 skip=11 rob=10 dp[i]=11	House 4: skipping keeps 11; robbing gives dp[2] + 3 = 10. Best 11 (skip it).
5	L5	i=5 skip=11 rob=12 dp[i]=12	House 5: skipping keeps 11; robbing gives dp[3] + 1 = 12. Best 12 (rob it).
6	L6	return=12 houses=[1, 3, 5]	Maximum loot 12. Tracing the take/skip decisions backwards from house 5 gives the houses [1, 3, 5].

23.06.4

Reverse iteration for 0/1 choice

The direction of the inner loop decides whether an item can be used **once or many times**. Iterating capacities **downwards** reads dp[w - weight] before it has been updated for this item, so the item is counted at most once: the 0/1 knapsack. Iterating **upwards** reads a value already updated for this item, so the item may be used again and again: the unbounded knapsack, and also the coin-change counting loop.

The animation makes it concrete. On items 1:15, 3:20, 4:30 with capacity 4 the correct backward loop gives 35, while the “1D forwards reuses the item” preset reports 60, which is the weight-1 item taken four times. Neither loop is a bug in general; each solves a different problem, and using the wrong direction silently solves the other one.

Java

1// identical except for the loop direction
2static int zeroOne(int[][] items, int capacity) {
3    int[] dp = new int[capacity + 1];
4    for (int[] it : items) for (int w = capacity; w >= it[0]; w--) dp[w] = Math.max(dp[w], dp[w - it[0]] + it[1]);
5    return dp[capacity];
6}
7
8static int unbounded(int[][] items, int capacity) {
9    int[] dp = new int[capacity + 1];
10    for (int[] it : items) for (int w = it[0]; w <= capacity; w++) dp[w] = Math.max(dp[w], dp[w - it[0]] + it[1]);
11    return dp[capacity];
12}

0/1 knapsack: 2D table, and why 1D must run backwards

Interactive · edit the input

grid · 5 × 6

012345

item \ cap

none

#1 (1:15)

#2 (3:20)

#3 (4:30)

Cell being computedCell it readsOn the tracebackWrong: item reused

Setup

Step 1 / 17

Java

1static int knapsack2D(int[] w, int[] v, int cap) {
2    int n = w.length; int[][] dp = new int[n + 1][cap + 1];            // dp[i][c]: best value from the first i items with capacity c
3    for (int i = 1; i <= n; i++)
4        for (int c = 0; c <= cap; c++) {
5            dp[i][c] = dp[i - 1][c];                                    // skip item i
6            if (c >= w[i - 1]) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // or take it
7        }
8    return dp[n][cap];
9}
10static int knapsack1D(int[] w, int[] v, int cap, boolean backwards) {
11    int[] dp = new int[cap + 1];
12    for (int i = 0; i < w.length; i++) {
13        if (backwards) for (int c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // right to left: dp[c - w] still excludes item i
14        else           for (int c = w[i]; c <= cap; c++) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // left to right: item i may be taken again (a bug for 0/1)
15    }
16    return dp[cap];
17}

Live state

items

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	items=3 capacity=4	dp[i][c] is the best value from the first i items with capacity c. Row 0 is all zeros. Each cell either skips item i (copy the cell above) or takes it (value + the cell above-left by the item's weight).
2	L6	item=1 c=0 skip=0 take=does not fit dp[i][c]=0	Item 1 (weight 1) does not fit in capacity 0: copy the cell above (0).
3	L6	item=1 c=1 skip=0 take=15 dp[i][c]=15	Capacity 1: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
4	L6	item=1 c=2 skip=0 take=15 dp[i][c]=15	Capacity 2: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
5	L6	item=1 c=3 skip=0 take=15 dp[i][c]=15	Capacity 3: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
6	L6	item=1 c=4 skip=0 take=15 dp[i][c]=15	Capacity 4: skip item 1 → 0; take it → 0 + 15 = 15. Keep 15.
7	L6	item=2 c=0 skip=0 take=does not fit dp[i][c]=0	Item 2 (weight 3) does not fit in capacity 0: copy the cell above (0).
8	L6	item=2 c=1 skip=15 take=does not fit dp[i][c]=15	Item 2 (weight 3) does not fit in capacity 1: copy the cell above (15).
9	L6	item=2 c=2 skip=15 take=does not fit dp[i][c]=15	Item 2 (weight 3) does not fit in capacity 2: copy the cell above (15).
10	L6	item=2 c=3 skip=15 take=20 dp[i][c]=20	Capacity 3: skip item 2 → 15; take it → 0 + 20 = 20. Keep 20.
11	L6	item=2 c=4 skip=15 take=35 dp[i][c]=35	Capacity 4: skip item 2 → 15; take it → 15 + 20 = 35. Keep 35.
12	L6	item=3 c=0 skip=0 take=does not fit dp[i][c]=0	Item 3 (weight 4) does not fit in capacity 0: copy the cell above (0).
13	L6	item=3 c=1 skip=15 take=does not fit dp[i][c]=15	Item 3 (weight 4) does not fit in capacity 1: copy the cell above (15).
14	L6	item=3 c=2 skip=15 take=does not fit dp[i][c]=15	Item 3 (weight 4) does not fit in capacity 2: copy the cell above (15).
15	L6	item=3 c=3 skip=20 take=does not fit dp[i][c]=20	Item 3 (weight 4) does not fit in capacity 3: copy the cell above (20).
16	L6	item=3 c=4 skip=35 take=30 dp[i][c]=35	Capacity 4: skip item 3 → 35; take it → 0 + 30 = 30. Keep 35.
17	L8	return=35 items=[#1, #2]	Best value 35. Traceback from the bottom-right cell: whenever a cell differs from the one above it, that item was taken (items [#1, #2]), and we move left by its weight.

Practice ladder

Now try it yourself

Easy

Pascal's Triangle II
Range Sum Query - Immutable

Medium

Longest Common Subsequence
Partition Equal Subset Sum
Coin Change II

Advanced

Ones and Zeroes
Target Sum

Key takeaways

If a row depends only on the previous row, keep two rolling rows.
A single row works when the loop order keeps still-needed values intact.
Eliminate a state dimension that is implied by others, after checking that no transition reads it.
Backwards iteration gives a 0/1 choice; forwards iteration allows unlimited reuse.