339. When does the greedy 'largest coin first' method for making change fail, and what do you use instead?
MediumGreedy algorithms
Show model answer
Greedy is optimal for canonical coin systems such as 1, 5, 10, 25, but not in general. With coins {1, 3, 4} and amount 6, greedy picks 4 + 1 + 1 (three coins) while 3 + 3 uses two. With {4, 10} and amount 12, greedy takes 10 and gets stuck, even though 4 + 4 + 4 works, so greedy can miss a solution entirely.
The safe method is dynamic programming: `best[x] = 1 + min(best[x - c])` over coins c, in O(k · amount) time and O(amount) space for k denominations. That is pseudo-polynomial because it depends on the numeric amount. To test whether a coin system is canonical, a classical result says that if greedy ever fails, a smallest failing amount exists below the sum of the two largest denominations, so you can compare greedy against DP over that finite range.