Coin Change and Counting

Given coin denominations, make a target amount. Three distinct questions, three different recurrences — mixing them up is the most common error in this family.

1. Minimum number of coins

$dp[w]=1+{\min }_{i}dp[w-c_i].$

vector<int> dp(W + 1, INT_MAX);
dp[0] = 0;
for (int w = 1; w <= W; w++)
    for (int c : coins)
        if (c <= w && dp[w - c] != INT_MAX)
            dp[w] = min(dp[w], dp[w - c] + 1);

$O(nW)$. Order of the loops does not matter here.

2. Number of combinations (order does not matter)

Coins on the outside, amount on the inside:

vector<long long> dp(W + 1, 0);
dp[0] = 1;
for (int c : coins)                          // coin loop OUTSIDE
    for (int w = c; w <= W; w++)
        dp[w] += dp[w - c];

Each coin type is fully processed before the next, so $\{1,2\}$ and $\{2,1\}$ are never both counted.

3. Number of permutations (order matters)

Amount on the outside, coins on the inside:

vector<long long> dp(W + 1, 0);
dp[0] = 1;
for (int w = 1; w <= W; w++)                 // amount loop OUTSIDE
    for (int c : coins)
        if (c <= w) dp[w] += dp[w - c];

The loop order is the semantics

Identical bodies, swapped loops, completely different answers. For target 3 with coins $\{1,2\}$: combinations gives 2 ($1+1+1$, $1+2$); permutations gives 3 ($1+1+1$, $1+2$, $2+1$). Read the statement carefully.

When greedy works

Greedy (always take the largest coin that fits) is not generally optimal: with coins $\{1,3,4\}$ and target 6, greedy gives $4+1+1=3$ coins but the optimum is $3+3=2$.

A coin system where greedy is always optimal is called canonical. Real currencies (including all common ones) are canonical, which is why the wrong intuition persists. Deciding whether a system is canonical is itself an interesting problem — Pearson’s algorithm does it in $O(n^3)$ by checking a bounded set of counterexample candidates.

Never assume greedy unless the problem states the denominations and you have verified them.

The variants

Question	Recurrence
Minimum coins	$dp[w]=1+\min dp[w-c]$
Number of combinations	coins outside, dp[w] += dp[w-c]
Number of permutations	amount outside
Is amount $w$ reachable?	boolean; use a bitset for $O(nW/64)$
Each coin used at most once	0/1 knapsack — weight loop downward
Each coin used at most $k_i$ times	bounded knapsack — binary splitting or monotone queue
Maximum coins with a value limit	knapsack with values
Which coins were used	store a from[w] array and walk back
Huge $W$, small coins	matrix exponentiation on the linear recurrence, or the Chicken McNugget / Frobenius structure
Count solutions modulo $p$	same DP, take everything mod $p$

The Frobenius / Chicken McNugget number

With two coprime coins $a,b$, the largest amount not representable is
$ab-a-b,$
and exactly $\frac{(a-1)(b-1)}{2}$ amounts are unrepresentable. For three or more coins there is no closed form, and computing the Frobenius number is NP-hard in general — though for small coin values a shortest-path formulation works:

Build a graph on residues mod $c_1$; edge from $r$ to $(r+c_i)\mathrm{mod}{c}_1$ with weight $c_i$. The shortest distance to residue $r$ is the smallest representable amount congruent to $r$. This “coin graph” / Dijkstra on residues technique answers “is $W$ representable” for $W$ up to $10^{18}$ in $O(c_{1}n\log c_1)$.

That trick is genuinely useful and worth remembering: when the target is astronomically large but the smallest coin is small, work modulo the smallest coin.

Related

• Classical Problems — the puzzle framings of the same question
• Knapsack — the general framework
• Subset Sum — the 0/1 feasibility version
• Generating functions — the counting version is the coefficient of $x^W$ in ${\prod }_i\frac{1}{1-x^{c_i}}$

See also: Knapsack · Partition Problems · Generating Functions