23.04Intermediate4 topics15 min4 interactive animations

Bottom-up tabulation

Bottom-up dynamic programming: iterating in dependency order, forward versus backward transitions, boundary handling and building the table.

Learning goals

Replace a recursion by loops that fill a table in dependency order
Write the same DP with pull (backward) and push (forward) transitions
Handle the boundaries of the table without out-of-range reads
Build a two-dimensional table and read off the answer

Prerequisites

Top-down memoization

Tabulation removes the recursion, the stack-depth limit and the call overhead, and makes the order of evaluation explicit.

23.04.1

Iterative dependency order

**Bottom-up** DP fills the table from the base cases upward, in an order where each cell's dependencies are already filled. For a recurrence on smaller indices that means a plain loop from small to large.

In the minimum-cost-climbing animation each cell is the cost of the step plus the cheaper of the two cells before it; the table fills left to right, every cell using only cells already written. The final answer is the minimum of the last two cells (the top is reached from either).

Java

1static int minCostBottomUp(int[] cost) {
2    int n = cost.length;
3    int[] dp = new int[n + 1];                   // dp[i]: cheapest way to stand at position i, where position n is the top
4    for (int i = 2; i <= n; i++) {
5        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);   // pay the step you leave
6    }
7    return dp[n];
8}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Min cost climbing stairs, with traceback

Interactive · edit the input

cost[i]

10i=0

15i=1

20i=2

5i=3

30i=4

8i=5

dp[i] = cheapest way to stand on i

10start

15start

?start

Setup

You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.

Step 1 / 7

Java

1static int minCost(int[] cost) {                 // you may start on step 0 or 1 and pay cost[i] when you leave step i
2    int n = cost.length; int[] dp = new int[n];  // dp[i] = cheapest total to stand on step i, including cost[i]
3    dp[0] = cost[0]; dp[1] = cost[1];
4    for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);   // best predecessor, then pay for this step
5    return Math.min(dp[n - 1], dp[n - 2]);        // the top is one step past the end, reached from either of the last two
6}

Live state

steps

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	steps=6	You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.
2	L4	i=2 dp[i-1]=15 dp[i-2]=10 dp[i]=30	dp[2] = cost[2] + min(15, 10) = 20 + 10 = 30. The cheaper predecessor is step 0 (remembered for the traceback).
3	L4	i=3 dp[i-1]=30 dp[i-2]=15 dp[i]=20	dp[3] = cost[3] + min(30, 15) = 5 + 15 = 20. The cheaper predecessor is step 1 (remembered for the traceback).
4	L4	i=4 dp[i-1]=20 dp[i-2]=30 dp[i]=50	dp[4] = cost[4] + min(20, 30) = 30 + 20 = 50. The cheaper predecessor is step 3 (remembered for the traceback).
5	L4	i=5 dp[i-1]=50 dp[i-2]=20 dp[i]=28	dp[5] = cost[5] + min(50, 20) = 8 + 20 = 28. The cheaper predecessor is step 3 (remembered for the traceback).
6	L5	top reached from=5 cost=28	The top (one step past the end) is cheapest from step 5: total 28.
7	L5	return=28 path=[1, 3, 5]	Minimum cost 28. Following the remembered predecessors backwards gives the steps stood on: [1, 3, 5].

23.04.2

Forward vs backward transitions

A transition can be written two ways. **Pull** (backward): compute dp[i] by looking at the states it comes from. **Push** (forward): once dp[i] is final, use it to update the states it leads to. They give the same table when the DAG is processed in topological order.

Use pull when each state has a small, clear list of predecessors; use push when each state has a clear list of successors, or when the sources are easier to enumerate than the destinations (counting paths in a graph, for instance). With push, every state must be final before it pushes, so the order still has to respect the dependencies.

Java

1// pull: ways[i] looks back at i - 1 and i - 2
2static long climbPull(int n) {
3    long[] ways = new long[n + 2];
4    ways[0] = 1;
5    for (int i = 1; i <= n; i++) ways[i] = ways[i - 1] + (i >= 2 ? ways[i - 2] : 0);
6    return ways[n];
7}
8
9// push: once ways[i] is final, add it to the states it leads to
10static long climbPush(int n) {
11    long[] ways = new long[n + 3];
12    ways[0] = 1;
13    for (int i = 0; i < n; i++) {
14        ways[i + 1] += ways[i];
15        ways[i + 2] += ways[i];
16    }
17    return ways[n];
18}

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.04.3

Boundary handling

Boundaries are where tabulated code breaks: the recurrence reads dp[i - 1] and dp[i - 2], which do not exist for the first cells. Three standard fixes: handle the first few cells as explicit **base cases**, add **padding** (a dummy cell dp[0] so every real cell can read the previous two), or guard each read with a condition.

Decode ways is a good test. dp[i] counts the ways to decode the first i characters. A single digit '1' to '9' contributes dp[i - 1]; a two-digit number from 10 to 26 contributes dp[i - 2]. A '0' cannot stand alone, so it contributes nothing as a single digit. With the padding cell dp[0] = 1, “226” gives 3 ways, “2101” gives 1 and “06” gives 0, because it starts with a zero.

Java

1static int numDecodings(String s) {
2    int n = s.length();
3    int[] dp = new int[n + 1];
4    dp[0] = 1;                                   // padding cell: the empty prefix has one decoding
5    for (int i = 1; i <= n; i++) {
6        int one = s.charAt(i - 1) - '0';
7        if (one >= 1) dp[i] += dp[i - 1];        // last character alone: 1..9
8        if (i >= 2) {
9            int two = (s.charAt(i - 2) - '0') * 10 + one;
10            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];   // last two characters together: 10..26
11        }
12    }
13    return dp[n];
14}

Decode ways: counting parses of a digit string

Interactive · edit the input

digits

dp[i] = decodings of the first i digits

1i=0

?i=1

?i=2

?i=3

Setup

dp[i] counts the ways to decode the first i digits. The last digit can be a letter by itself (1-9, never 0), or the last two digits can form a letter 10-26.

Step 1 / 5

Java

1static int numDecodings(String s) {                  // 'A'=1 ... 'Z'=26
2    int n = s.length(); int[] dp = new int[n + 1];     // dp[i] = ways to decode the first i digits
3    dp[0] = 1;                                         // the empty prefix has one decoding
4    for (int i = 1; i <= n; i++) {
5        if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];                            // last digit alone (1-9)
6        if (i >= 2 && s.charAt(i - 2) != '0' && Integer.parseInt(s.substring(i - 2, i)) <= 26) dp[i] += dp[i - 2];   // last two digits (10-26)
7    }
8    return dp[n];
9}

Live state

digits

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	digits=3	dp[i] counts the ways to decode the first i digits. The last digit can be a letter by itself (1-9, never 0), or the last two digits can form a letter 10-26.
2	L5	i=1 dp[i]=1	dp[1] = 1: '2' alone adds dp[0] = 1.
3	L6	i=2 dp[i]=2	dp[2] = 2: '2' alone adds dp[1] = 1; "22" is a letter and adds dp[0] = 1.
4	L6	i=3 dp[i]=3	dp[3] = 3: '6' alone adds dp[2] = 2; "26" is a letter and adds dp[1] = 1.
5	L8	return=3	3 ways to decode "226". O(n) time; only the last two dp values are needed, so O(1) space is possible.

23.04.4

Table construction

Two-dimensional tables follow the same rules: define the state (i items considered, w capacity), fill the base row and column, and fill the rest in an order that has every dependency done. For the 0/1 knapsack, dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value) where the second option only exists when the item fits.

The “2D table” preset takes items of (weight:value) 1:15, 3:20 and 4:30 with capacity 4, fills a 4 × 5 table row by row and ends with 35, by taking items #1 and #2 (weights 1 and 3 for 15 + 20). The single item #3 (weight 4) is worth 30, less than 35. Each cell depends on the row above only, a fact the optimisation lessons use to shrink the table.

Java

1// items: {weight, value}; returns the best total value within the capacity
2static int knapsack(int[][] items, int capacity) {
3    int n = items.length;
4    int[][] dp = new int[n + 1][capacity + 1];   // dp[i][w]: best value using the first i items with capacity w
5    for (int i = 1; i <= n; i++) {
6        int weight = items[i - 1][0], value = items[i - 1][1];
7        for (int w = 0; w <= capacity; w++) {
8            dp[i][w] = dp[i - 1][w];                                           // skip the item
9            if (weight <= w) dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight] + value);   // take it
10        }
11    }
12    return dp[n][capacity];
13}

Best

O(nW)

Average

O(nW)

Worst

O(nW)

Space

O(nW)

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.

Practice ladder

Now try it yourself

Easy

Climbing Stairs
Pascal's Triangle

Medium

Unique Paths II
Decode Ways
Minimum Path Sum

Advanced

Partition Equal Subset Sum
Cherry Pickup

Key takeaways

Bottom-up DP fills the table from the base cases in dependency order, with no recursion.
Pull computes a cell from its sources; push sends a finished cell to its successors.
Handle boundaries with explicit base cases, padding cells or guarded reads.
A 2D table is filled row by row; each knapsack cell depends only on the row above.