DP problems — Fibonacci, coin change (count + min), 0 - 1 knapsack: Visual walkthrough

Step 0 — What is the actual question?

Before any math, picture the situation.

Look at the figure: three items sit outside a bag labelled "capacity $W = 7$ ". We must decide, for each, in or out. That is $2^{n}$ possible subsets — for $n = 30$ that is a billion. We want to be cleverer than checking all of them.

Step 1 — Turn the choice into a question we can repeat

WHAT. We attack ONE item at a time. Line the items up as item 1, item 2, …, item $n$ . Stand in front of item $i$ and ask a single yes/no question: do I put item $i$ in the bag?

WHY. A yes/no question has only two branches. If we can solve "best value using items $1.. i$ with a bag of size $w$ " by only looking at "best value using items $1.. i - 1$ ", we have chopped one item off the problem — a strictly smaller problem of the same shape. That is the whole trick of dynamic programming: recursion where every call is a shrunk copy of the original.

PICTURE.

The tree shows the very first fork. The left branch (blue) = "skip item $i$ ". The right branch (orange) = "take item $i$ ". Notice both children now talk only about items $1.. i - 1$ — item $i$ is finished with the moment we decide. That is the seed of everything below.

We name the answer to the shrunk problem:

$dp [i] [w] = best total value using only items 1.. i, with a bag of capacity w$

Term by term:

$i$ — how many items we are allowed to consider (a prefix $1.. i$ ).
$w$ — how much bag capacity we currently have to spend, $0 \leq w \leq W$ .
$dp [i] [w]$ — the number we are hunting: the maximum value obtainable under those two limits.

Step 2 — The "skip" branch

WHAT. Suppose we decide not to take item $i$ .

WHY. If item $i$ never goes in, then whatever value we end up with came entirely from items $1.. i - 1$ , and the bag capacity is untouched — still $w$ . So the best we can do is exactly the best we could already do with one fewer item and the same room:

$answer if we skip dp [i] [w] = same room, one fewer item dp [i - 1] [w]$

$i - 1$ — item $i$ is gone from the menu, so we drop back to the previous prefix.
$w$ (unchanged) — skipping costs no weight, so capacity stays the same.

PICTURE.

The blue arrow points straight up one row (from row $i$ to row $i - 1$ ) and stays in the same column $w$ . Straight up = "one fewer item"; same column = "capacity unspent". That vertical arrow is the skip rule.

Step 3 — The "take" branch

WHAT. Now suppose we do take item $i$ .

WHY. Two things happen the instant item $i$ enters the bag:

We gain its value $v_{i}$ .
We spend $w_{i}$ of our capacity, leaving only $w - w_{i}$ for everything else. And "everything else" must come from items $1.. i - 1$ (because item $i$ is used up — this is the 0/1 rule: no second copy). So:

$answer if we take dp [i] [w] = value we gain v_{i} + previous items only dp [i - 1] [shrunken room w - w_{i}]$

$v_{i}$ — the reward for putting item $i$ in; added once.
$i - 1$ — again we fall back a row, because item $i$ can't be reused.
$w - w_{i}$ — the bag now has less room; we ask the sub-problem about the reduced capacity.

Guard condition. This branch only makes sense if the item fits: we need $w_{i} \leq w$ . If $w_{i} > w$ the item is too heavy for the current bag, so "take" is impossible and only the skip branch survives.

PICTURE.

The orange arrow goes up one row AND left by $w_{i}$ columns (from column $w$ to column $w - w_{i}$ ), then we add $v_{i}$ on top. Up = fewer items; left = spent capacity; the " $+ v_{i}$ " label rides on the arrow = the value collected.

Step 4 — Combine: take the better of the two branches

WHAT. We have two candidate values for $dp [i] [w]$ : the skip value and the take value. We keep whichever is larger, because we want maximum value.

WHY $max$ and not $+$ ? These two branches are mutually exclusive decisions for the same cell — item $i$ is either in or out, never both. So we do not add them; we choose the winner. $max$ answers exactly "which single decision leaves me richer?"

$dp [i] [w] = max (skip (Step 2) dp [i - 1] [w], take (Step 3), only if w_{i} \leq w v_{i} + dp [i - 1] [w - w_{i}])$

PICTURE.

Both arrows from Steps 2 and 3 now feed into the same target cell (green). The little " $max$ " gate keeps the taller bar. Every cell in the whole table is filled by this one gate — that is the entire algorithm.

Base row. Row $i = 0$ means "zero items allowed". With no items you can put nothing in, so the value is $0$ for every capacity $w$ : $dp [0] [w] = 0$ . That is the floor the whole table stands on.

Step 5 — Fill the whole table, watch a real example

WHAT. Fill row by row, left to right, using only the two arrows. Example from the parent: $w = [1, 3, 4, 5], v = [1, 4, 5, 7], W = 7$

WHY row order. Each cell $dp [i] [w]$ only ever looks at row $i - 1$ (both arrows go up). So as long as the previous row is complete before we start the current row, every value we need is already there. No cell is ever read before it is written.

PICTURE.

The colour-shaded grid is the finished table. Trace the bottom-right corner $dp [4] [7] = 9$ . The winning path (highlighted) came from taking item 2 (weight 3, value 4) and item 3 (weight 4, value 5): $3 + 4 = 7$ weight exactly, $4 + 5 = 9$ value. Because every "take" arrow drops a row, item 2 and item 3 are each used once — the 0/1 promise is kept automatically.

Step 6 — Squeeze two rows into one (and why the loop reverses)

WHAT. Notice each new row reads only the row directly above. So we never need the whole 2D grid — one 1D array dp[w] that we overwrite as we process each item is enough.

WHY reverse the inner loop. When we overwrite a single row in place, the cell we read, $dp [w - w_{i}]$ , must still hold the old (previous-item) value — never the freshly updated current-item value. If we go left→right, we would update $dp [w - w_{i}]$ before reading it, so item $i$ could sneak in twice. Going right→left (from $W$ down to $w_{i}$ ) guarantees $dp [w - w_{i}]$ is still the previous item's value when we use it.

PICTURE.

Top strip: forward iteration — the red arrow reads a cell to its left that was already refreshed this round, so item $i$ leaks in again (that is unbounded knapsack, see Unbounded Knapsack and Rod Cutting). Bottom strip: backward iteration — the green arrow always reads a cell that is still "old", so each item enters at most once. Same code, one loop direction apart.

Step 7 — Every edge case, shown

WHAT & WHY. A correct derivation must survive the weird inputs. Here they are:

$W = 0$ (bag holds nothing): the take branch needs $w_{i} \leq 0$ , impossible for positive weights, so every cell is $0$ . Answer $= 0$ . (leftmost panel)
No items ( $n = 0$ ): the base row is the whole table; answer $= 0$ . (second panel)
An item heavier than the bag ( $w_{i} > W$ ): its take arrow would leave column $w - w_{i} < 0$ , which does not exist — so that item can never be taken and only its skip arrow fires. (third panel — item shown greyed out)
A zero-value item ( $v_{i} = 0$ ): taking it adds $+ 0$ but eats weight, so $max$ will only ever pick it if it does no harm; it never hurts the optimum. (rightmost panel)
All items fit together ( $\sum w_{i} \leq W$ ): every take branch is available, so the optimum is simply $\sum v_{i}$ — the bag is never the bottleneck.

Because the recurrence is max(skip, take-if-fits) with a base of all-zeros, none of these cases needs special code — they fall out of the same two arrows. That robustness is the payoff of deriving it instead of memorising it.

The one-picture summary

One target cell, two arrows, one $max$ gate, one base row of zeros — repeated across a grid, then folded into a single backward-swept array. Everything on this page is that picture.

Recall Feynman retelling — explain the walkthrough to a 12-year-old

Line your toys up. Carry a backpack that can hold a certain weight. Walk to the first toy and ask two things: "If I leave it, how happy am I with the toys behind me and this much room?" — that is looking straight up in the grid. "If I grab it, I get its fun points but my backpack has less room left for the earlier toys" — that is looking up-and-left, then adding the fun points. Keep whichever answer makes you happier. Do this for every toy against every possible amount of room, writing each answer on a sticky note so you never redo it. When you re-use one sticky-note row to save paper, fill it in from the biggest room down to the smallest, so you never accidentally count the same toy twice. The last sticky note, bottom-right, is your best possible happiness.

Recall

Why does the "take" arrow go to row $i - 1$ and not row $i$ ? ::: Because in 0/1 knapsack each item is used at most once; after taking item $i$ we must continue with only the earlier items. Why $max$ instead of adding the two branches? ::: Skip and take are two mutually exclusive decisions for the same cell; we pick the better one, we don't do both. In the 1D version, why iterate weight from $W$ down to $w_{i}$ ? ::: So that $dp [w - w_{i}]$ still holds the previous item's value when read, preventing an item from being taken twice. What is $dp [0] [w]$ and why? ::: $0$ for all $w$ — with zero items allowed you can pack nothing, so no value.

See also: Tabulation vs Memoization · Time and Space Complexity · Subset Sum and Partition Problems · Greedy Algorithms · parent topic.