---
title: Coin Change & Unbounded Knapsack
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 5
order: 805
summary: |
  The previous lesson let each item be taken at most once. Drop that cap — items
  may be reused _any number of times_ — and the 0/1 knapsack collapses from a
  two-dimensional table to a one-dimensional one, because there is no longer a
  prefix of "already-used" items to track. We meet **unbounded knapsack**, then
  its most famous instance, **coin change**: the minimum-coins recurrence
  $C[a] = 1 + \min_c C[a-c]$, and the counting variant where the _order of the
  loops_ decides whether you count unordered combinations or ordered sequences —
  the classic bug. Greed fails in general but works for canonical coin systems.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming"
  - book: Skiena
    ref: "§ — Knapsack / Coin Change"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
practice:
  - title: 'Coin Change'
    slug: coin-change
    difficulty: Medium
  - title: 'Coin Change II'
    slug: coin-change-ii
    difficulty: Medium
  - title: 'Combination Sum IV'
    slug: combination-sum-iv
    difficulty: Medium
  - title: 'Perfect Squares'
    slug: perfect-squares
    difficulty: Medium
  - title: 'Word Break'
    slug: word-break
    difficulty: Medium
---

The previous lesson solved [0/1 knapsack](/algorithms/dynamic-programming/knapsack), where each item is taken whole or left
behind, _at most once_. The "0/1" in the name was the include/exclude bit on
every item, and it forced a two-dimensional table $K(i, w)$: we had to remember
_which prefix of items_ was still on the table, because once item $i$ was used it
could not be used again. Now relax exactly that constraint. Let every item be
available in **unlimited supply**, so the thief may pack as many copies of item
$i$ as fit. This is the **unbounded knapsack problem**, and allowing
infinite copies removes one whole dimension from the
[dynamic program](/algorithms/dynamic-programming/principles)'s table.

In 0/1 knapsack the second index $i$ existed to stop us from reusing an
item; whether item $i$ had already been taken was genuine state. When items may be
reused without limit, that question is meaningless (the set of available items
never shrinks), so the only thing a subproblem needs to remember is **how much
capacity is left**. One number, one dimension.

## Unbounded knapsack: one dimension instead of two

> **Input:** $n$ item types with positive integer weights $w_1, \dots, w_n$ and
> values $v_1, \dots, v_n$, an integer capacity $W$, and an _unlimited_ supply of
> each type.
> **Output:** the maximum total value of a multiset of items whose weights sum to
> at most $W$.

Define the subproblem on capacity alone:

> **Definition (Knapsack value).** Let $K[w]$ be the maximum value achievable with weight budget exactly $w$, using
> any number of copies of any item type.

The answer is $K[W]$ (or $\max_{w \le W} K[w]$ if we want "at most $W$"; padding
with a zero-value, weight-one item makes them equal). To fill $K[w]$, consider the
**last item placed** into the knapsack. It is some type $i$ with $w_i \le w$; after
placing it we have value $v_i$ plus the best we can do with the _remaining_ budget
$w - w_i$, and that remaining budget may itself use type $i$ **again**:
$$
K[w] = \max_{i\,:\,w_i \le w}\ \parens{v_i + K[w - w_i]},
\qquad K[0] = 0.
$$

Compare the right-hand side to 0/1 knapsack's
$\max\parens{K(i-1,w),\ v_i + K(i-1, w-w_i)}$. There the include branch read
$K(i-1, \cdot)$, the previous row, item $i$ _removed from the pool_. Here the
include branch reads $K[w - w_i]$, the **same** $K$, item $i$ _still in the pool_.
That one difference is the whole distinction between "use once" and "use any number
of times."

> **Remark (Why the loop order differs from 0/1 knapsack).** In the space-optimized 0/1
> version we kept a single array $K[\cdot]$ and swept the budget _downward_
> ($w = W, \dots, 0$) precisely so that $K[w - w_i]$ still held the _previous_
> row's value, the value _before_ item $i$ was available, guaranteeing each item
> was used at most once. For unbounded knapsack we want the opposite: $K[w - w_i]$
> should already reflect item $i$ being usable. So we sweep the budget _upward_
> ($w = 0, \dots, W$); by the time we reach $w$, the cell $K[w - w_i]$ has already
> been updated _in this same pass_ and may itself contain a copy of item $i$.
> Ascending weight is what permits reuse.

The figure below folds one item of weight $2$ into a single array and contrasts the
two sweep directions. Ascending, cell $K[w]$ reads $K[w-2]$ _after_ that cell was
already touched this pass, so an item can chain into itself (reuse). Descending,
$K[w]$ reads $K[w-2]$ while it still holds the pre-pass value, so each item lands at
most once.

$$
% caption: One item of weight $2$ folded into a 1-D array. Ascending sweep (top):
%          $K[w]$ reads an already-updated $K[w-2]$, so the item can be reused. Descending
%          sweep (bottom): $K[w]$ reads the old $K[w-2]$, so the item is used at most once.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{no}{HTML}{C0392B}
  % ---- ascending (unbounded, reuse) ----
  \node[lbl] at (-1.9,1.0) {ascending};
  \node[lbl, align=left] at (-1.9,0.5) {(reuse OK)};
  \foreach \w in {0,...,5} { \node[lbl] at (1.2*\w,1.55) {$w{=}\w$}; }
  \foreach \w in {0,...,5} { \node[cell] (u\w) at (1.2*\w,0.85) {}; }
  \draw[->, thick, acc] (u0.north) to[bend left=40] (u2.north);
  \draw[->, thick, acc] (u2.north) to[bend left=40] (u4.north);
  \node[lbl, acc] at (3.0,2.35) {read after update = reuse};
  % ---- descending (0/1, no reuse) ----
  \node[lbl] at (-1.9,-1.0) {descending};
  \node[lbl, align=left] at (-1.9,-1.5) {(no reuse)};
  \foreach \w in {0,...,5} { \node[cell] (d\w) at (1.2*\w,-0.85) {}; }
  \draw[->, thick, no] (d3.south) to[bend right=40] (d5.south);
  \draw[->, thick, no] (d1.south) to[bend right=40] (d3.south);
  \node[lbl] at (3.0,-2.35) {\textcolor{no}{read before update = used once}};
\end{tikzpicture}
$$

Because the available-item set never changes, the item loop and the weight loop
may be nested in either order; there is no "previous row" to respect, only the
ascending-weight rule. We fill $W + 1$ cells, each scanning up to $n$ items:

$$
\Theta(nW)
$$

time, the same as 0/1 knapsack, but in $\Theta(W)$ **space**: one array, no second
dimension to collapse.

::impl{algo="unbounded_knapsack"}

## Coin change — minimum coins

The cleanest instance of unbounded knapsack strips the values away, just as
subset-sum stripped them from 0/1 knapsack. Fix a set of coin denominations
$c_1, \dots, c_n$, available in unlimited supply, and an amount $A$. Ask: **what is
the fewest coins that sum to exactly $A$?**

This is unbounded knapsack with every item's value set to $1$ (one coin) and the
objective flipped to _minimize_: we want the smallest count, not the largest
value. Let $C[a]$ be the minimum number of coins summing to amount $a$:

$$
C[a] =
\begin{cases}
0 & \text{if } a = 0, \\[3pt]
1 + \displaystyle\min_{c\,:\,c \le a}\ C[a - c] & \text{if } a > 0, \\[3pt]
+\infty & \text{if no } c \le a \text{ reaches a finite value.}
\end{cases}
$$

The $1 + (\cdots)$ pays for the coin we just placed; the $\min$ over denominations
$c \le a$ picks the best amount to reach the shortfall $a - c$. An amount that no
combination of coins can hit keeps the sentinel value $+\infty$, which propagates:
if every $C[a-c]$ is $\infty$ then so is $C[a]$. The figure below shows the 1-D table
filling left to right, each cell reaching back $c$ positions for each denomination.

$$
% caption: The 1-D coin-change table fills left to right; cell $C[a]$ reads back $c$
%          positions for coin $c$, taking $1 + C[a-c]$ (the highlighted transition uses
%          coin $c=3$).
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % amount header
  \foreach \a in {0,...,6} { \node[lbl] at (\a,0.7) {$a{=}\a$}; }
  % cells C[0..6] for coins {1,3,4}, values 0 1 2 1 1 2 2
  \node[cell] at (0,0) {$0$};
  \node[cell] at (1,0) {$1$};
  \node[cell] at (2,0) {$2$};
  \node[cell] (src) at (3,0) {$1$};
  \node[cell] at (4,0) {$1$};
  \node[cell] at (5,0) {$2$};
  \node[cell, fill=acc!18] (dst) at (6,0) {$2$};
  \node[lbl] at (-1.1,0) {$C[a]$};
  % transition arrow C[6] <- 1 + C[3] using coin c=3
  \draw[->, thick, red!75!black] (src.south) to[bend right=38] node[below, draw=none, font=\footnotesize, red!75!black] {$+1$ coin $c{=}3$} (dst.south);
  \node[lbl, anchor=south, align=center, fill=white, inner sep=1.5pt] at (6,1.5) {$C[6]$\\$={}1{+}C[3]$};
\end{tikzpicture}
$$

**A full table, cell by cell.** Take coins $\{1, 3, 4\}$ and fill $C[0..6]$ left to
right. Each cell tries all three denominations and keeps the smallest $1 + C[a-c]$;
the winning coin is recorded in $prev[a]$ for reconstruction.

- $C[0] = 0$ — empty pile, no coins. $prev[0]$ undefined.
- $C[1] = 1 + C[0] = 1$; only coin $1$ fits. $prev[1] = 1$.
- $C[2] = 1 + C[1] = 2$; again only coin $1$ fits. $prev[2] = 1$.
- $C[3] = 1 + \min(C[2],\,C[0]) = 1 + \min(2,\,0) = 1$; coin $3$ wins over three
  ones. $prev[3] = 3$.
- $C[4] = 1 + \min(C[3],\,C[1],\,C[0]) = 1 + \min(1,\,1,\,0) = 1$; coin $4$ wins.
  $prev[4] = 4$.
- $C[5] = 1 + \min(C[4],\,C[2],\,C[1]) = 1 + \min(1,\,2,\,1) = 2$; coins $1$ or $4$
  tie, e.g. $4 + 1$. $prev[5] = 4$.
- $C[6] = 1 + \min(C[5],\,C[3],\,C[2]) = 1 + \min(2,\,1,\,2) = 2$; coin $3$ wins,
  landing on $C[3] = 1$. $prev[6] = 3$.

The finished tables:

| $a$        | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| ---------- | - | - | - | - | - | - | - |
| $C[a]$     | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
| $prev[a]$  | – | 1 | 1 | 3 | 4 | 4 | 3 |

So $C[6] = 2$, achieved by $3 + 3$: two coins, not the three a careless greedy pick
($4 + 1 + 1$) would take. The next figure fills the same array with every winning
transition drawn in, so the whole computation is visible at once.

$$
% caption: The finished min-coins array for coins $\{1,3,4\}$, amounts $0..6$, with the
%          traceback for $C[6]$: follow $prev[6]=3$ to $C[3]$, then $prev[3]=3$ to $C[0]$,
%          spending coin $3$ twice. The $prev$ value sits under each traced cell.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  opt/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \a in {0,...,6} { \node[lbl] at (1.5*\a,0.75) {$a{=}\a$}; }
  \node[cell] (c0) at (0,0) {$0$};
  \node[cell] (c1) at (1.5,0) {$1$};
  \node[cell] (c2) at (3.0,0) {$2$};
  \node[opt]  (c3) at (4.5,0) {$1$};
  \node[cell] (c4) at (6.0,0) {$1$};
  \node[cell] (c5) at (7.5,0) {$2$};
  \node[opt]  (c6) at (9.0,0) {$2$};
  \node[lbl] at (-1.35,0) {$C[a]$};
  % prev row under each cell
  \foreach \x/\p in {0/-,1/1,2/1,3/3,4/4,5/4,6/3} {
    \node[lbl, text=black] at (1.5*\x,-0.85) {\p}; }
  \node[lbl, text=black] at (-1.35,-0.85) {\textit{pre\/v}};
  % traceback for C[6]: 6 -> 3 -> 0, both hops coin 3, arcs dip below the prev row
  \draw[->, very thick, acc] (c6.south) to[out=-70, in=-70, looseness=1.1]
    node[pos=0.5, below=1pt, draw=none, font=\scriptsize, acc] {coin 3} (c3.south);
  \draw[->, very thick, acc] (c3.south) to[out=-110, in=-70, looseness=1.1]
    node[pos=0.5, below=1pt, draw=none, font=\scriptsize, acc] {coin 3} (c0.south);
\end{tikzpicture}
$$

The $prev$ row under the array records the winning coin at each amount. The two blue
arrows are the traceback for amount $6$: from $C[6]$ follow $prev[6]=3$ to $C[3]$,
then $prev[3]=3$ to $C[0]$ — coin $3$ twice, the two shaded cells.

```algorithm
caption: $\textsc{Min-Coins}(c[1..n], A)$ — fewest coins summing to amount $A$
number: 1
$C[0] \gets 0$
for $a \gets 1$ to $A$ do
  $C[a] \gets +\infty$ // unreachable so far
  $prev[a] \gets \text{nil}$
  for $i \gets 1$ to $n$ do
    if $c[i] \le a$ and $C[a - c[i]] + 1 < C[a]$ then
      $C[a] \gets C[a - c[i]] + 1$
      $prev[a] \gets c[i]$ // coin that closed the gap
return $C[A]$ // $+\infty$: $A$ unreachable
```

The outer loop runs over $A$ amounts and the inner over $n$ coins, so the running
time is $\Theta(nA)$ in $\Theta(A)$ space, [pseudo-polynomial](/algorithms/foundations/asymptotic-analysis) in the sense
of the previous lesson: polynomial in the numeric _value_ $A$ but exponential in
its bit length.[^skiena-coin]

**Reconstruction.** The value $C[A]$ is the coin _count_; the coins themselves come
from the $prev$ array. Starting at $a = A$, the denomination $prev[a]$ is the last
coin used, so emit it and jump to $a - prev[a]$; repeat until $a = 0$.

```algorithm
caption: $\textsc{Recover-Coins}(prev, A)$ — list the coins of an optimal solution
number: 2
$a \gets A$;  $S \gets \langle\,\rangle$
while $a > 0$ do
  $S \gets S \cup \set{prev[a]}$ // coin that closed $a$
  $a \gets a - prev[a]$
return $S$
```

::impl{algo="min_coins"}

## Coin change — counting combinations

A different question on the same coins: not _how few_ coins, but _how many distinct
ways_ to make amount $A$. This is **Coin Change II**, and it counts **multisets** of
coins. $\{1,1,1,1\}$ and $\{1,3\}$ are two ways to make $4$, but $\{1,3\}$ and
$\{3,1\}$ are the _same_ way, because a multiset has no order. Let $N[a]$ be the
number of such combinations summing to $a$, with $N[0] = 1$ (the empty multiset is
the one way to make $0$).

The naive recurrence "$N[a] = \sum_{c \le a} N[a-c]$" is **wrong** for combinations;
it counts $1{+}3$ and $3{+}1$ separately. The fix is structural and is the most
famous loop-order subtlety in dynamic programming.

> **Remark (Loop order decides what you count).**
> - **Coins outer, amount inner** — process one denomination at a time, folding all
>   of its copies into the table before moving to the next coin — counts **unordered
>   combinations** (multisets). This is Coin Change II.
> - **Amount outer, coins inner** — at each amount, sum over every coin that could
>   come _last_ — counts **ordered sequences** (compositions). This is Combination
>   Sum IV.[^cs-loop]

Coins-outer avoids the double count because each denomination is introduced
exactly once and never revisited: every multiset is built in a _fixed canonical
order_ of denominations (coin $c_1$ first, then $c_2$, and so on), so each multiset
is reached by exactly one path through the loops. The amount-outer loop, by
contrast, considers every coin as the possible last coin at every amount, so the
same multiset is counted once for each ordering of its coins.

$$
% caption: Coins-outer combination fill for $\{1,2\}$. After folding in coin $1$ every
%          amount has one way (all ones); folding in coin $2$ adds
%          $N[a] \mathrel{+}= N[a-2]$, giving $N[3]=2$ without ever double-counting
%          $1{+}2$ and $2{+}1$.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  upd/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-2.1,0) {after coin $1$};
  \foreach \v/\x in {1/0,1/1,1/2,1/3} { \node[cell] (a\x) at (\x,0) {$\v$}; }
  \foreach \x in {0,...,3} { \node[lbl] at (\x,0.72) {$a{=}\x$}; }
  \node[lbl] at (-2.1,-2.3) {after coin $2$};
  \foreach \v/\x/\s in {1/0/cell,1/1/cell,2/2/upd,2/3/upd} { \node[\s] (b\x) at (\x,-2.3) {$\v$}; }
  \draw[->, thick, acc] (a0.south) to[bend right=20] (b2.north);
  \draw[->, thick, acc] (a1.south) to[bend right=20] (b3.north);
  \node[lbl, acc] at (3.9,-1.15) {N[a] += N[a-2]};
\end{tikzpicture}
$$

Because coin $2$ is introduced only after coin $1$ is fully folded in, each
multiset is built in the fixed order "ones first, then twos," so $N[3]=2$ counts
$\{1,1,1\}$ and $\{1,2\}$ once apiece; a $2{+}1$ ordering is never generated.

```algorithm
caption: $\textsc{Count-Combinations}(c[1..n], A)$ — number of multisets summing to $A$
number: 3
$N[0..A] \gets 0$;  $N[0] \gets 1$
for $i \gets 1$ to $n$ do          // coins outer: combinations
  for $a \gets c[i]$ to $A$ do     // amount inner, ascending: reuse
    $N[a] \gets N[a] + N[a - c[i]]$
return $N[A]$
```

Swapping the two loops (`for a` outside, `for i` inside) computes
$N[a] = \sum_{i\,:\,c_i \le a} N[a - c_i]$ instead, the **ordered** count (Combination
Sum IV), where $1{+}3$ and $3{+}1$ are distinct. Same body, same $\Theta(nA)$ time;
the nesting alone flips the meaning.

**A ways table, one coin at a time.** Coins $\{1, 2, 5\}$, amount $A = 5$. Start with
$N = [1,0,0,0,0,0]$ (only the empty bag makes $0$), then fold in each coin, updating
$N[a] \mathrel{+}= N[a-c]$ for $a$ ascending from $c$ to $5$.

| after folding | $N[0]$ | $N[1]$ | $N[2]$ | $N[3]$ | $N[4]$ | $N[5]$ |
| ------------- | ------ | ------ | ------ | ------ | ------ | ------ |
| _start_       | 1      | 0      | 0      | 0      | 0      | 0      |
| coin $1$      | 1      | 1      | 1      | 1      | 1      | 1      |
| coin $2$      | 1      | 1      | 2      | 2      | 3      | 3      |
| coin $5$      | 1      | 1      | 2      | 2      | 3      | 4      |

After coin $1$ every amount has a single all-ones bag. Folding in coin $2$ adds, for
each $a \ge 2$, the ways that end with (i.e. include) a $2$, so $N[4]$ becomes $3$:
$1{+}1{+}1{+}1$, $2{+}1{+}1$, $2{+}2$. Folding in coin $5$ touches only $N[5]$,
adding the single bag $\{5\}$: $N[5] = 4$, namely $1{\times}5$, $2{+}1{+}1{+}1$,
$2{+}2{+}1$, and $5$. Because each coin is folded in exactly once, no bag is ever
counted under two orderings.

### A worked count: combinations vs sequences

Take coins $\{1, 2\}$ and amount $A = 3$. As an unordered count the answers are
$\{1,1,1\}$ and $\{1,2\}$: **two** combinations. As an ordered count we also
distinguish the arrangements of $\{1,2\}$, giving $1{+}1{+}1$, $1{+}2$, and $2{+}1$,
for **three** sequences. The figure traces both, and ties each to its loop order.

$$
% caption: Coins $\{1,2\}$, amount $3$: the multiset count (2, coins-outer loop) is less
%          than the ordered count (3, amount-outer loop), because $1{+}2$ and $2{+}1$
%          collapse to one combination.
\begin{tikzpicture}[
  >=Stealth,
  box/.style={draw, minimum width=20mm, minimum height=6mm, font=\small, inner sep=2pt},
  hd/.style={draw=none, font=\small},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % left column: combinations
  \node[hd] (h1) at (0,0) {2 combinations (as bags)};
  \node[lbl] at (0,-0.55) {coins outer, amount inner};
  \node[box] (a1) at (0,-1.3) {$1{+}1{+}1$};
  \node[box, fill=acc!18] (a2) at (0,-2.1) {$1{+}2$};
  % right column: sequences
  \node[hd] (h2) at (4.6,0) {3 ordered sequences};
  \node[lbl] at (4.6,-0.55) {amount outer, coins inner};
  \node[box] (b1) at (4.6,-1.3) {$1{+}1{+}1$};
  \node[box, fill=acc!18] (b2) at (4.6,-2.1) {$1{+}2$};
  \node[box, fill=acc!18] (b3) at (4.6,-2.9) {$2{+}1$};
  % the single combination {1,2} corresponds to two sequences
  \draw[->, thick, acc] (a2.east) -- (b2.west);
  \draw[->, thick, acc] (a2.east) -- (b3.west);
  \node[lbl, acc] at (2.3,-3.5) {the bag $1{+}2$ -> two orderings};
\end{tikzpicture}
$$

The blue link shows the discrepancy: the single combination $\{1,2\}$ on
the left corresponds to the two ordered sequences $1{+}2$ and $2{+}1$ on the right.
Counting the left column is the coins-outer loop; counting the right is amount-outer.
Picking the wrong nesting silently computes the wrong quantity — no error, just a
wrong number — which is why it is the classic bug.

::impl{algo="count_coin_change"}

## Why greedy fails — and when it works

Coin change has a natural [greedy heuristic](/algorithms/greedy/the-greedy-method): repeatedly take the **largest coin
that fits**. For the U.S. currency system it always gives the minimum, which is why
cashiers can make change without dynamic programming.

> **Claim.** Largest-coin-first greedy is _not_ optimal for general coin systems.

> **Proof.** Take coins $\{1, 3, 4\}$ and amount $6$. Greedy grabs the $4$, then
> must finish with $1 + 1$, for three coins. Yet $3 + 3$ makes $6$ in two coins,
> so greedy is not optimal. $\qed$

Largest-coin-first leaves a remainder ($2$) that the denominations
cover badly, while a less greedy first step ($3$) leaves a remainder the coins cover
perfectly.

$$
% caption: Greedy change-making fails on $\{1,3,4\}$ for amount $6$: largest-coin-first
%          takes $4{+}1{+}1$ (three coins), while the DP optimum is $3{+}3$ (two coins).
\begin{tikzpicture}[
  >=Stealth,
  coin/.style={draw, circle, minimum size=8mm, inner sep=0pt, font=\small},
  pick/.style={coin, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-1.95,0) {greedy};
  \node[coin, fill=red!14] at (0,0) {$4$};
  \node[coin, fill=red!14] at (0.95,0) {$1$};
  \node[coin, fill=red!14] at (1.9,0) {$1$};
  \node[lbl] at (3.6,0) {$3$ coins};
  \node[lbl] at (-1.95,-1.2) {optimal};
  \node[pick] at (0,-1.2) {$3$};
  \node[pick] at (0.95,-1.2) {$3$};
  \node[lbl, acc] at (3.6,-1.2) {$2$ coins};
\end{tikzpicture}
$$

A coin system is called **canonical** when the greedy algorithm is optimal for every
amount; standard currencies (like $\{1, 5, 10, 25\}$) are deliberately designed to be
canonical so that greedy change-making works. Whether an _arbitrary_ system is
canonical is itself a nontrivial question (it can be decided by checking greedy
against the DP optimum over a bounded range of amounts), but the safe default for an
unknown denomination set is the $C[a] = 1 + \min_c C[a-c]$ dynamic program, which is
correct for _any_ coins.[^skiena-greedy]

> **Intuition.** Greedy commits to the biggest coin and never reconsiders, so it
> can be left with a remainder its denominations can only pay in many small coins.
> The DP keeps _every_ amount's best answer, so a worse-looking first coin can
> still lead to the optimum — the optimal-substructure argument greedy
> lacks here but possesses on canonical systems.

::impl{algo="greedy_change"}

## The same shape elsewhere: Perfect Squares and Word Break

Coin change is unbounded knapsack, and two well-known problems are the
_identical_ recurrence with the coins renamed.

**Perfect Squares** asks for the fewest perfect squares ($1, 4, 9, 16, \dots$)
summing to $n$. That is $\textsc{Min-Coins}$ all over again, with the "coins" being the
squares $\le n$:
$$
S[k] = 1 + \min_{j^2 \le k}\ S[k - j^2], \qquad S[0] = 0.
$$
The squares are reusable (you may use $1$ four times to make $4$), so it is the
ascending-weight minimization we already wrote; only the denomination set changes.

**Word Break** asks whether a string $s$ can be segmented into dictionary words. The
"coins" are now _words_, the "amount" is a _string prefix_, and the table is indexed
by prefix length. Let $B[k]$ be true if the first $k$ characters of $s$ split into
dictionary words:
$$
B[k] = \bigvee_{\substack{w \in \text{dict} \\ s[k - |w| + 1\,..\,k] = w}} B[k - |w|],
\qquad B[0] = \text{true}.
$$
It is the _boolean_ ($\lor$) flavor, like subset-sum was to knapsack, where a word
$w$ ending at position $k$ plays the role of a coin of "value" $|w|$ landing the
prefix on the earlier boundary $k - |w|$. The empty prefix $B[0]$ is the
always-reachable base, exactly like $C[0] = 0$.

::impl{algo="perfect_squares,word_break"}

## Canonical systems, Frobenius, and generating functions

The claim that "greedy works on canonical systems" rests on a subtle
theory. Deciding whether an arbitrary $n$-coin system is canonical was open for years;
Pearson (2005) gave an $O(n^3)$ test, and Kozen and Zaks (1994) showed the smallest
counterexample — the least amount where greedy fails — always lies below
$c_{n-1} + c_n$ (the sum of the two largest coins), so a canonical system can be
certified by checking greedy against the DP only up to that bound. The everyday
$\{1,5,10,25\}$ is canonical by design, but even small tweaks break it: the once-real
British pre-decimal system and hypothetical sets like $\{1,3,4\}$ are not, which is
exactly why a cash register that must handle _arbitrary_ denominations falls back to
the DP.

Coin change also touches classical number theory. The **Frobenius problem** — given
coprime denominations, what is the largest amount that _cannot_ be made at all? —
asks which cells of the DP table stay $\infty$. For two coins $a, b$ the answer
is the closed form $ab - a - b$ (the Frobenius number, or Chicken McNugget number),
but for three or more coins no closed form is known and computing it is NP-hard in
general (Ramírez Alfonsín, 1996). The reachable set (which amounts have $C[a] <
\infty$) is eventually periodic with period $\gcd$, a structure the DP table
exhibits numerically.

The counting variant connects to **generating functions** from partition
theory. The number of ways to make amount $a$ with coins $\{c_1,
\dots, c_n\}$ is the coefficient of $x^a$ in $\prod_i \frac{1}{1 - x^{c_i}}$, and the
coins-outer DP loop is precisely the term-by-term multiplication of these geometric
series — folding in one factor $\frac{1}{1 - x^{c_i}}$ per coin. When the coins are
all positive integers $1, 2, 3, \dots$, this product is Euler's partition generating
function, and the DP becomes a way to compute the **partition numbers** $p(n)$ (the
subject of Hardy and Ramanujan's famous asymptotic $p(n) \sim \frac{1}{4n\sqrt3}
e^{\pi\sqrt{2n/3}}$). The Word Break instance, meanwhile, is the recognition problem
for a language over a finite dictionary, and its natural generalization — count or
weight the segmentations — reproduces the forward algorithm of a **weighted
finite-state** model, which underlies tokenization and word segmentation.[^coin-beyond]

## Takeaways

- **Unbounded knapsack** lets each item be used _any number of times_. That single
  change deletes the item dimension: the subproblem $K[w]$ depends only on remaining
  capacity, giving the 1-D recurrence $K[w] = \max_{w_i \le w}(v_i + K[w - w_i])$ in
  $\Theta(nW)$ time and $\Theta(W)$ space, versus 0/1 knapsack's 2-D $K(i,w)$.
- The include branch reads $K[w - w_i]$ at the **same** item-availability (not the
  previous row), so we sweep weight **ascending** to _permit_ reuse, the exact
  opposite of 0/1's descending sweep, which _forbids_ it.
- **Coin change (min coins)** is unbounded knapsack with unit values and a $\min$
  objective: $C[a] = 1 + \min_{c \le a} C[a - c]$, $C[0] = 0$, $\infty$ if
  unreachable; a $prev$ array reconstructs the coins.
- **Counting** ways is governed by **loop order**: _coins outer, amount inner_ counts
  **unordered combinations** (Coin Change II); _amount outer, coins inner_ counts
  **ordered sequences** (Combination Sum IV). Same code, different question: the
  classic bug.
- **Greedy** (largest coin first) fails in general ($\{1,3,4\}$, amount $6$: greedy
  $4{+}1{+}1$, optimal $3{+}3$) but is correct for **canonical** systems like
  standard currency; the DP is correct for _any_ denominations.
- **Perfect Squares** (squares as coins) and **Word Break** (dictionary words as
  coins over string prefixes) are the same unbounded-DP shape.

[^skiena-coin]: **Skiena**, § — Knapsack / Coin Change: making change as unbounded knapsack, $\Theta(nA)$ and pseudo-polynomial in the amount.
[^cs-loop]: **Erickson**, Ch. — Dynamic Programming: combinations vs. compositions and how the nesting of the item and target loops selects between unordered and ordered counts.
[^skiena-greedy]: **Skiena**, § — Knapsack / Coin Change: greedy change-making is optimal only for canonical denomination systems; the DP is correct for arbitrary coins.
[^coin-beyond]: **Kozen & Zaks** (1994) bound the smallest greedy-counterexample below $c_{n-1}+c_n$, and **Pearson** (2005) gives an $O(n^3)$ canonicity test; **Ramírez Alfonsín** (1996) on the NP-hardness of the Frobenius number. The counting DP is the coefficient extraction of $\prod_i (1-x^{c_i})^{-1}$, Euler's partition generating function.