Coin change

Why it exists

Problem: You want to make a target amount using the fewest coins possible. A greedy algorithm (picking the largest coin first) fails if the denominations aren't neat multiples.

Better idea: For every amount from 1 up to the target, try every coin. The best answer for `amount` is 1 plus the best answer for `amount - coin`.

Mental model

Build the cheapest way to make 1 cent, then 2 cents, all the way up to the target, using smaller answers as stepping stones.

Let `dp[amt]` represent the minimum number of coins to make `amt`. The base case is `dp[0] = 0`. For all other amounts, we initialize them to `infinity` (an unreachable sentinel). The transition tries every coin: `dp[amt] = min(dp[amt], 1 + dp[amt - coin])`. This is an UNBOUNDED reuse DP because each coin can be used many times.

Repeated decision: For this amount, does using this coin (1 + the best answer for amount-coin) beat what I already had for this amount?

Explanation

Coin Change is the classic counterexample to the Greedy algorithm.

As we saw in the greedy section, if your coins are `{1, 3, 4}` and your target is `6`, greedy picks `4` then `1` then `1` (3 coins). Dynamic Programming tries all paths and correctly finds `3 + 3` (2 coins).

To trace building `dp[]` up to `6`:

- `dp[0] = 0`

- `dp[1] = 1` (using 1)

- `dp[2] = 2` (using 1+1)

- `dp[3] = 1` (using 3)

- `dp[4] = 1` (using 4)

- `dp[5] = 2` (using 4+1)

- `dp[6] = 2` (using 3+3)

At `dp[6]`, we check `1 + dp[6-1] = 1 + dp[5] = 3`, `1 + dp[6-3] = 1 + dp[3] = 2`, and `1 + dp[6-4] = 1 + dp[2] = 3`. The minimum is `2`.

If `dp[target]` remains infinity at the end, it means no combination of coins can form the amount, so we return `-1`.

Key points

Complexity: O(amount * number of coins) time, O(amount) space.
Unbounded reuse: Unlike 0/1 choices where an item is consumed, we check `dp[amt - coin]` which might have already used the same coin. This allows infinite reuse.

Common mistakes

Applying a greedy algorithm: Assuming that taking the largest possible coin is always optimal. This only works for specific coin systems (like US currency), not arbitrary denominations.
Forgetting the unreachable sentinel: If an amount cannot be made, its value should remain `infinity`. If you initialize with 0 or -1, `min()` comparisons will pick up invalid paths. Don't forget to handle the sentinel when returning the final answer.

Recall questions

What does `dp[amt]` represent in the Coin Change problem?
What is the recurrence relation for Coin Change?
Why is the base array initialized with infinity?

Questions & answers

How would you find the total number of unique combinations that make the target amount, rather than the minimum coins?

Change the state definition to 'combinations' and the transition to a sum: `dp[amt] += dp[amt - coin]`. Initialize `dp[0] = 1`.

Approach: Recognize the shift from finding an optimal path (`min`) to counting all paths (`+`).

What if you had a limited supply of each coin?

This becomes the 0/1 Knapsack problem. You must add a second dimension to the state (which coins you have considered) or iterate backwards to prevent unbounded reuse.

Approach: Identify that restricting reuse fundamentally changes the DP state from 1D to a 2D choice.