Coin Change

Coin Change: given coin denominations coins and a target amount, return the fewest coins that add up to amount, using each denomination as many times as you like. If no combination works, return -1.

Examples: coins = [1, 2, 5], amount = 11 returns 3 (5 + 5 + 1). coins = [2], amount = 3 returns -1.

Taking the largest coin that fits looks right for [1, 2, 5], but it fails in general: for [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 (three coins) while 3 + 3 uses two. Trying every combination recursively is correct but exponential — and it recomputes the same remaining amounts again and again, which is exactly what a DP table removes.

Any way of making amount a ends with some last coin c. Before it, you had to make a - c — as cheaply as possible. So:

dp[a] = min(dp[a - c] + 1) over every coin c ≤ a.

1. dp[0] = 0; every other amount starts at ∞ (not reachable yet).
2. Fill dp[1], dp[2], … dp[amount] in order, so dp[a - c] is always already known.
3. Return dp[amount], or -1 if it is still ∞.

Trying every coin as the last one is what makes this correct where greedy is not.

The dp table runs left to right. For each amount, every coin is tried in turn, and the cell it reads — dp[a − coin] — is marked; when that gives fewer coins, the new count is written. The last step traces the answer's coins back through the table.