The Problem#
You have an unlimited supply of coins in denominations given by an array coins, and a target amount. Find the fewest coins that sum to exactly amount. If no combination reaches the target, return -1.
This looks superficially like a greedy problem: take the largest coin that fits, repeat. But greedy fails on many coin sets. With denominations [1, 3, 4] and amount 6, greedy picks 4 then 1+1 for three coins, while DP finds 3+3 for two.