Coin Change
Medium· unbounded knapsack
Problem
You have unlimited coins of several denominations. Return the fewest coins needed to make up an exact amount, or -1 if that amount cannot be formed.
Examples
Input: coins = [1,2,5], amount = 11
Output: 3
5 + 5 + 1.
Input: coins = [2], amount = 3
Output: -1
Constraints
- • 1 <= coins.length <= 12
- • 1 <= coins[i] <= 2^31 - 1
- • 0 <= amount <= 10^4
Hints & approach
Hint 1
Greedy (always take the biggest coin) fails for some coin sets.
Hint 2
Think of the last coin used to make amount a.
Hint 3
min[a] = 1 + min over coins c of min[a - c].
Approachtry the hints first
This is an unbounded knapsack minimising count. Let dp[a] be the fewest coins summing to a, with dp[0] = 0 and all others set to infinity. For each a from 1 to amount, try every coin c ≤ a and set dp[a] = min(dp[a], dp[a-c] + 1). If dp[amount] is still infinity, return -1.
Time O(n·amount) · Space O(amount)