Tabulation (bottom-up DP) — iterative: Visual walkthrough

We use the parent's own example the whole way through:

Everything below is built on one idea from Optimal Substructure: the best answer for the whole bag is made of best answers for smaller bags with fewer items. We just have to write those smaller answers down first — that is tabulation.

Step 1 — Draw the table and name what a box means

WHAT. We make a grid. Rows = "how many items are we allowed to use", columns = "how big is the bag right now".

WHY. Before writing any number, a DP must answer "what does one box mean?" If a box has no clear English meaning, every later step is guesswork. We define:

$d p [i] [c] = best total value using only the first i items i items, if the bag holds at most capacity c weight.$

$i$ ranges $0, 1, 2, 3$ — $i = 0$ means "you're allowed no items".
$c$ ranges $0, 1, 2, 3, 4$ — $c$ is a pretend smaller capacity, not always the real $4$ . We need these smaller bags because taking an item shrinks the room left.

PICTURE. The empty grid. Look at the labels: every cell is a question ("best value with these many items and this much room?") waiting for an answer.

Figure — Tabulation (bottom-up DP) — iterative

Step 2 — Fill the base row (zero items = zero value)

WHAT. Fill the entire top row $i = 0$ with $0$ .

WHY. With no items allowed, there is nothing to put in the bag, no matter how big the bag is. So the best value is $0$ for every capacity:

$d p [0] [c] = 0 for all c .$

$d p [0] [c]$ — the row where zero items are permitted.
$= 0$ — empty bag, empty value.

This is the recurrence's seed. Without it, every later cell that "looks back" would read an empty box and the whole build collapses. This is exactly the parent's warning: forget the base case and everything stays 0 or crashes — except here 0 is correct, which is why we set it on purpose.

PICTURE. The green base row of zeros. Every arrow later in the derivation eventually traces back to this row.

Step 3 — The choice that makes every other cell: take it or skip it

WHAT. For any cell $d p [i] [c]$ we imagine standing in front of item $i$ with a bag that holds $c$ . We have exactly two moves.

WHY. Every item is either in the bag or out. Those two possibilities cover everything and never overlap — so the best answer is the better of the two:

$d p [i] [c] = max (skip item i d p [i - 1] [c], take item i v_{i} + d p [i - 1] [c - w_{i}])$

Read each piece slowly:

$d p [i - 1] [c]$ — skip: pretend item $i$ doesn't exist. Same bag $c$ , but now only the first $i - 1$ items. The room $c$ is untouched.
$v_{i}$ — the reward we grab by taking item $i$ .
$c - w_{i}$ — the room left over after item $i$ eats its weight $w_{i}$ .
$d p [i - 1] [c - w_{i}]$ — the best we can still do in that leftover room with the earlier items.
$max (\dots)$ — we don't know which move is better in advance, so we compute both and keep the winner.

PICTURE. The two branches drawn as arrows out of one cell: the skip arrow reaches straight up, the take arrow reaches up-and-left by $w_{i}$ columns and adds $v_{i}$ .

Step 4 — The guard: what if the item is too heavy?

WHAT. Before the $max$ , we must check: does item $i$ even fit?

WHY. The "take" branch reads $d p [i - 1] [c - w_{i}]$ . If $w_{i} > c$ , then $c - w_{i}$ is negative — a bag with negative room, which is nonsense (and in code an out-of-bounds index). So when the item is too heavy, taking is not an option and only skipping survives:

$d p [i] [c] = {d p [i - 1] [c] max (d p [i - 1] [c], v_{i} + d p [i - 1] [c - w_{i}]) if w_{i} > c (doesn’t fit) if w_{i} \leq c (fits)$

The top line is the degenerate case — no choice, just carry the value from above.
The bottom line is the full two-way choice from Step 3.

This is a case we must cover explicitly, or the reader hits a negative index they never saw handled.

PICTURE. Two mini-cells side by side: one where the item is heavier than the bag (only the up arrow is legal, the take arrow is crossed out in red), one where it fits (both arrows legal).

Step 5 — Fill row 1 (only item 1 available, weight 1, value 1)

WHAT. Compute $d p [1] [c]$ for $c = 0, 1, 2, 3, 4$ , reading only from the zero-row above.

WHY. Item 1 has weight $w_{1} = 1$ , value $v_{1} = 1$ .

$c = 0$ : bag holds nothing, item weight $1 > 0$ → doesn't fit → $d p [1] [0] = d p [0] [0] = 0$ .
$c = 1$ : fits. $max (d p [0] [1], 1 + d p [0] [1 - 1]) = max (0, 1 + 0) = 1$ .
$c = 2, 3, 4$ : item still fits, and the leftover room adds nothing new (only one item exists), so each is $max (0, 1 + 0) = 1$ .

Row 1: $[0, 1, 1, 1, 1]$ .

PICTURE. Row 1 filled, with the arrow for $d p [1] [1]$ shown: skip-branch reads the $0$ above, take-branch reaches up-left one column, reads $0$ , adds $v_{1} = 1$ , wins.

Step 6 — Fill row 2 (item 2 now allowed, weight 3, value 4)

WHAT. Compute $d p [2] [c]$ , reading only from row 1 (already done in Step 5).

WHY. Item 2 has $w_{2} = 3$ , $v_{2} = 4$ .

$c = 0, 1, 2$ : $w_{2} = 3 > c$ → doesn't fit → copy from above: $d p [2] [c] = d p [1] [c] = 0, 1, 1$ .
$c = 3$ : fits. $max (d p [1] [3], 4 + d p [1] [3 - 3]) = max (1, 4 + d p [1] [0]) = max (1, 4 + 0) = 4$ .
$c = 4$ : fits. $max (d p [1] [4], 4 + d p [1] [4 - 3]) = max (1, 4 + d p [1] [1]) = max (1, 4 + 1) = 5$ .

Row 2: $[0, 1, 1, 4, 5]$ .

Notice $d p [2] [4] = 5$ : that's item 1 and item 2 together (value $1 + 4$ ), and the recurrence found it automatically by adding $v_{2}$ to the leftover-room answer $d p [1] [1] = 1$ .

PICTURE. Row 2 filled. The star cell $d p [2] [4]$ shows its take-arrow reaching up-left by $w_{2} = 3$ columns into $d p [1] [1]$ , plus the $+ 4$ .

Step 7 — Fill row 3 and read the answer (item 3, weight 4, value 5)

WHAT. Compute the last row $d p [3] [c]$ , reading only from row 2. The final answer lives at $d p [3] [4]$ .

WHY. Item 3 has $w_{3} = 4$ , $v_{3} = 5$ .

$c = 0, 1, 2, 3$ : $w_{3} = 4 > c$ → doesn't fit → copy row 2: $0, 1, 1, 4$ .
$c = 4$ : fits. $max (d p [2] [4], 5 + d p [2] [4 - 4]) = max (5, 5 + d p [2] [0]) = max (5, 5 + 0) = 5$ .

Row 3: $[0, 1, 1, 4, 5]$ .

The answer is $d p [3] [4] = 5$ . Here is the subtle, beautiful part: it's a tie. Taking item 3 alone gives $5$ ; the previous row already had $5$ (items 1+2). The $max$ keeps $5$ either way — both plans are optimal. This is the tie the parent hinted at, now derived, not asserted.

PICTURE. Full table, bottom-right corner glowing amber as the answer, with both winning routes (item 3 alone; items 1+2) traced.

Step 8 — Why the fill order can never go backwards

WHAT. We always filled row by row, top to bottom ( $i$ small → large).

WHY. Every cell $d p [i] [c]$ reads only from row $i - 1$ . So when we start row $i$ , row $i - 1$ is already 100% complete. This is the whole reason tabulation loops small → large, the exact reverse of how memoization recurses down from the top. Break this order — fill row 3 before row 2 — and you'd read empty boxes: the parent's first "steel-manned mistake" made visible.

PICTURE. The dependency picture: an arrow from row $i - 1$ (solid, "already done") up into row $i$ (being filled), with a red X on any attempt to read a not-yet-filled cell.

The one-picture summary

Everything at once: the zero base row seeds the table; each cell picks max(skip, take); "take" hops up-and-left by the item's weight and adds its value; the guard blocks the hop when the item is too heavy; rows fill top-to-bottom; the corner holds the answer $5$ .

Recall Feynman: the whole walkthrough in plain words

Picture a grid of boxes. The top row is all zeros — "no items, no value, done." Now go down one row at a time. For each box you ask one question: "Item on this row — do I grab it or leave it?" Leaving it means "copy the box directly above me." Grabbing it means "jump up one row, then slide left by however much this item weighs, take whatever value is written there, and add this item's value on top." You keep whichever of the two numbers is bigger. If the item is heavier than the room you're pretending to have, you can't grab it — you just copy from above. Because every box only ever looks at the row above it, you must fill rows from the top down, so the row you look at is already finished. When the last row's last box is filled, that number — the bottom-right corner — is the best value the whole bag can hold. For our items it's 5.

Active recall

What does the cell dp[i][c] mean in words?

The best total value using only the first

i

items with a bag that holds at most capacity

c

Why is the whole top row dp[0][c] set to 0?

With zero items allowed there is nothing to put in the bag, so the best value is 0 for every capacity — this seeds the table.

In dp[i][c] = max(skip, take), what is the "take" term?

v_{i} + d p [i - 1] [c - w_{i}]

— grab item

i

's value, then use the best answer for the leftover room

c - w_{i}

with the earlier items.

Why must we guard with if w_i <= c before the take branch?

Otherwise

c - w_{i}

is negative — a bag with negative room, a nonsense state and an out-of-bounds index.

For our example, what is dp[3][4] and why is it a tie?

5 — item 3 alone gives 5, and items 1+2 also give 5, so the max keeps 5 either way.

Why fill the table top row to bottom row?

Each cell reads only from the row above, so that row must be fully computed first (dependencies before use).

Connections

Tabulation (bottom-up DP) — iterative (index 3.7.8) — the parent this page derives in pictures
0-1 Knapsack — the problem we filled out cell by cell
Optimal Substructure — why "best whole = best of sub-answers" is legal here
Overlapping Subproblems — why writing answers in the table pays off
Recurrence Relations — the math of the take/skip formula
Space Optimization in DP — collapse this 2D grid to one row (then iterate capacity high→low)
Memoization (top-down DP) — the same recurrence, filled in the reverse order

Visual walkthrough — Tabulation (bottom-up DP) — iterative