You are given coin denominations and a target amount. Using an unlimited supply of each coin, find the minimum number of coins that sum exactly to the amount.
The first line contains the integer amount.
The second line contains the integer m, the number of coin types.
The third line contains m positive integers: the coin denominations.
The minimum number of coins that make amount, or -1 if it cannot be made. (Making an amount of 0 needs 0 coins.)
Example 1
11 3 1 2 5
3
5 + 5 + 1 = 11 uses 3 coins, the fewest possible.
Example 2
3 2 2 4
-1
No combination of 2s and 4s makes 3, so -1.
Example 3
0 1 7
0
Amount 0 needs 0 coins.
A greedy "take the biggest coin first" strategy does NOT always work — e.g. coins {1, 3, 4} for amount 6.
Let best[a] be the fewest coins for amount a. Build it up from 0: best[a] = 1 + min over coins c <= a of best[a - c].
Initialise best[0] = 0 and every other amount as "infinity"; if best[amount] is still infinity at the end, the answer is -1.
Bottom-up dynamic programming. best[0] = 0; for each amount a from 1 to target, best[a] = 1 + min(best[a - c]) over coins c <= a. The answer is best[amount], or -1 if unreachable.
import sys
data = list(map(int, sys.stdin.read().split()))
amount = data[0]
m = data[1]
coins = data[2:2 + m]
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
print(dp[amount] if dp[amount] != INF else -1)
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.