Coin Change
Given coin denominations and a target amount, return the fewest coins needed to make exactly that amount, using any coin as often as you like. Return -1 if the amount cannot be formed.
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2^31 - 1
- 0 ≤ amount ≤ 10^4
- Minimum count with unlimited reuse — unbounded knapsack
- Greedy by largest coin fails (e.g. coins 1, 3, 4 for amount 6)
- Optimal solution for amount a builds on amount a − coin
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Define dp[a] as the minimum coins for amount a, with dp[0] = 0 and everything else infinity. For each amount from 1 to the target and each coin ≤ that amount, set dp[a] = min(dp[a], dp[a - coin] + 1). The answer is dp[amount] or -1 if it stayed infinite. Each amount is built from a strictly smaller amount plus one coin, so the table fills bottom-up.
- BFS over amounts where each coin is an edge finds the minimum in the same complexity and stops early. Memoized recursion is equivalent but risks deep stacks.