Problem. Given coin denominations coins and an amount, return the fewest coins that add up to the amount, using any
number of each coin, or −1 if it can't be made.
coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
coins = [2], amount = 3 → −1
coins = [1, 3, 4], amount = 6 → 2 (3 + 3; greedy takes 4 + 1 + 1)
The state is the amount still to make. Whatever the last coin c is, the rest must be made optimally, so best(a) = 1 + min over c of best(a − c). Lesson 8.5 listed every combination that sums to a target; here we only want the smallest, which turns an exponential search into a table of size amount.
ML context. Making an exact total from a fixed set of sizes appears in systems work: composing a global batch from the micro-batch sizes a kernel is tuned for (Change D), filling a memory budget with block sizes an allocator offers, or splitting a request across instance types. The greedy "biggest piece first" is tempting there too, and fails for the same reason.