How few coins can make a target amount from an unlimited supply of given denominations? If coins are [1, 3, 4] and the target is 7, the answer is 2 (3 + 4).

Unlike 0/1 Knapsack, each coin type may be reused without bound — the “unbounded” flavor of the knapsack family. That changes exactly where the DP looks for its subproblems.

How It Works

The table dp[i][a] stores the minimum number of coins using only the first i denominations to make amount a:

1. Initialize: dp[0][0] = 0; every other amount is impossible with no coins, so it starts as ∞ (the “impossible” sentinel).
2. Skip: not using the current coin gives dp[i-1][a].
3. Take: using one more of the current coin gives dp[i][a - coin] + 1 — note the same row, because you may use the current coin again.
4. Choose: store the minimum:

   dp[i][a] = min(dp[i-1][a], dp[i][a - coin] + 1)

Key Insight

The one-character difference from 0/1 Knapsack is where “take” reads from:

• Coin Change: dp[i][a - coin] — same row, unbounded.
• 0/1 Knapsack: dp[i-1][w - weight] — previous row.

Same-row access is what lets a single coin be used many times. The ∞ sentinel makes “impossible” contagious: any amount that can’t be formed stays ∞ forever, and the final answer is dp[n][A].

Worked Example

The visualizer uses coins [1, 3, 4] and target 7:

The bottom-right cell reads 2, and the backtrack reveals one 3¢ and one 4¢ — 3 + 4 = 7. This is exactly the answer the visualizer’s final step reports.

Edge Cases & Pitfalls

• Unreachable amount — if the target can’t be formed (e.g. coins [2, 4], target 7), dp[n][7] stays ∞: report “impossible”, not a huge number.
• Amount 0 — the answer is 0 (use no coins); the sentinel row makes this automatic.
• Why greedy fails — coins [1, 3, 4], amount 6: greedy takes 4 then 1+1 = 3 coins; the optimum is 3+3 = 2 coins. The ratio heuristic breaks on non-canonical denominations.
• Huge amounts — O(nA) is pseudo-polynomial: like knapsack, it’s exponential in the bit-length of A.

Comparison: 0/1 Knapsack vs Coin Change

Applications

• Change-making — vending machines and payment systems
• Budgeting — hitting an exact spend with a set of denominations
• Word segmentation / partitioning — picking minimum-cost splits over a set of pieces

Practice Trajectory

1. Hand-fill the table for [1, 3, 4] / target 7 and confirm the bottom-right value.
2. Explain why “take” reads from the same row, and what would change for 0/1 semantics.
3. Reconstruct which coins produce the optimum.
4. Predict what happens to amount 2 if the 1¢ coin is removed.
5. Reduce to a 1D O(A) array and confirm you still get 2 for target 7.