Coin Change
The coin change problem asks for the minimum number of coins from a set of denominations that sum to a target amount, assuming unlimited coins of each value. A related version counts how many distinct ways the amount can be formed.
Why greedy can fail
Always grabbing the largest coin works for some currencies but not all. With coins of one, three, and four, making six greedily takes four then one then one for three coins, while two threes do it in two. So greedy is not always optimal.
Dynamic programming
Build an array where each index is an amount and the value is the fewest coins to make it:
- Start with zero coins for amount zero.
- For every amount, try each coin and take one plus the best result for the remaining amount.
The final cell holds the answer, or a sentinel if the amount cannot be formed.
Key idea
Build minimum coin counts from small amounts up, trying every denomination at each step.