Coin Change
Problem statement
You get a list of coin denominations coins, with an unlimited supply of each, and a target amount. Return the smallest number of coins that add up to exactly amount, or -1 if no combination does. An amount of 0 needs 0 coins.
The obvious greedy strategy, always taking the largest coin that fits, fails for some coin sets. For coins [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 (3 coins) but 3 + 3 uses 2.
Examples
Example 1
Input: coins = [2,5,10], amount = 27
Output: 4
Explanation: 10 + 10 + 5 + 2. Three coins can reach 25 or 30, but not 27.
Example 2
Input: coins = [4,6], amount = 9
Output: -1
Explanation: Every coin is even, so no mix of them adds up to an odd amount.
Hints
Approach
Bottom-up table. Let dp[a] be the fewest coins for amount a. Set dp[0] = 0 and every other entry to amount + 1, a value larger than any real answer (you never need more than amount coins, since the smallest coin is at least 1).
For a from 1 to amount, and for each coin c <= a, set dp[a] = min(dp[a], dp[a - c] + 1). Smaller amounts are always finished before they're needed. At the end, dp[amount] > amount means impossible.
O(amount · k)Space O(amount)def coin_change(coins, amount): dp = [0] + [amount + 1] * amount for a in range(1, amount + 1): for c in coins: if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1 return -1 if dp[amount] > amount else dp[amount] print(coin_change([2, 5, 10], 27))print(coin_change([4, 6], 9))Follow-up questions
- Return which coins make up the best answer (store the last coin used for each amount and walk back).
- Each coin type now has a limited count. How does the table change? (Bounded knapsack.)
Frequently asked questions
It is the most common medium DP problem, and a fair stand-in for resource packing: the fewest instances of fixed sizes that exactly meet a capacity target, or the fewest batches to reach a count. It also tests whether you notice that greedy fails, which matters when you design allocation logic.
Coin systems like 1, 2, 5, 10 are designed so that greedy is always optimal (they are called canonical). Arbitrary sets like [1, 3, 4] are not. Unless you can prove a set is canonical, you need DP.
That is Coin Change II. Use ways[0] = 1 and loop over coins in the outer loop and amounts in the inner loop, adding ways[a - c]. Putting coins outside counts each combination once regardless of order.