Coin Change
Medium· unbounded knapsack
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
