Coin Change — Blind 75 practice

Problem

Given coin denominations coins and a target amount, return the fewest coins that sum exactly to amount. You have unlimited coins of each denomination.
If the amount cannot be made, return -1. An amount of zero needs zero coins.

Examples

Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 5 + 5 + 1.

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0

Example 4:
Input: coins = [186,419,83,408], amount = 6249
Output: 20

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 10^4
0 <= amount <= 10^4

Prerequisites

Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence.
Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.

How to think about it

1. Fewest Coins for Every Amount Below Optimal

Intuition

best[a] means "the fewest coins that make exactly a" — say that sentence and the recurrence writes itself: try each coin as the LAST one used and take the cheapest of best[a - coin] + 1. Greedy largest-first is the trap, and [186,419,83,408] is in the tests because it fails there: taking the biggest coin can strand the remainder.

Algorithm

1. best[0] is zero coins; every other amount starts unreachable.
2. For each amount upward, try every coin that fits.
3. Take the cheapest of best[amount - coin] + 1.
4. An amount still unreachable at the end answers -1.

Time & Space

Time O(amount x coins). Space O(amount).