How do you find the minimum number of coins that make a given amount?
You build a table where each entry says the fewest coins you need to make that amount, and you fill it from the smallest amount up.
def coin_change(coins, amount):
table = [0] + [float('inf')] * amount
for value in range(1, amount + 1):
for coin in coins:
if coin <= value:
table[value] = min(table[value], table[value - coin] + 1)
if table[amount] == float('inf'):
return -1
return table[amount]
So how does it work? The entry table[value] holds the fewest coins that make that amount. The entry for zero is zero, because you need no coins to make nothing. And every other entry starts at infinity, because at first you do not know whether that amount can be made at all.
And then you go through the amounts from one up. For each amount you try every coin, and you ask whether using that coin last is better than what you already have. The amount that is left over is the amount minus the coin, and so the number of coins is one plus the answer for that smaller amount.
the coins 1, 3, 4 the amount is 6
the table
0 0
1 1
2 2
3 3
4 4
5 5
6 6
the answer is 6, because 3 and 3 make it with two coins
And there is a detail worth knowing about. The table only holds one coin at a time, so the order of the coins does not matter and the same combination is never counted twice. That is what makes this version different from the combination counting version in the next question.
And the answer is minus one when the amount cannot be made at all. That happens when the amount is not a multiple of the biggest coin, for example with the coins 5 and 10 and the amount of seven.
And the complexity is O of amount times the number of coins for the time, and O of amount for the space.
So the rule to remember is this. For each amount, try every coin as the last one.
The next two questions in this topic show the counting version and the version for a huge amount.