Coin Change
Hard · rating 1700 · dp, greedy
The first line contains the target amount and the number of coin types k. The second line contains k coin denominations. Print the minimum number of coins that sum to exactly amount, or -1 if it is impossible. You may use each denomination any number of times.
Constraints: 0 ≤ amount ≤ 104, 1 ≤ k ≤ 20
Editorial
Approach (dynamic programming)
Let dp[a] be the fewest coins summing to a. Start with dp[0] = 0 and everything else infinity. For each amount try every coin: dp[a] = min(dp[a], dp[a - coin] + 1). The answer is dp[amount], or -1 if it stayed infinite.
dp = [0] + [inf]*amount
for a in range(1, amount+1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] if dp[amount] != inf else -1Note
Greedy (largest coin first) fails for arbitrary denominations, so DP is needed for the general case.
Complexity
Time: O(amount × coins). Space: O(amount).