Coin Change
Dynamic Programming: lesson 5 of 10
Fewest pieces to hit a target, one amount at a time.
Lesson 5 of 10 · 6 min
Coin Change
Step 1 of 13
best[a] is the fewest coins that make exactly a. Start with best[0] = 0 and every other amount at ∞.
The Idea
Build the answer for every amount from 1 up to the target. The fewest pieces making amount a is one more than the fewest making a minus some coin, so try each coin and keep the smallest result. Amounts nothing can reach stay at infinity, which is exactly how the function knows to report failure.
Real-World Example
A banquet hall seating a party of 46 from tables of four, six, and ten. Fewer tables means more dance floor, so the manager works upward from small parties: once the answer for 36 is on the sheet, adding one ten-seater settles 46 immediately.
The Code
def fewest(coins, target):
INF = float("inf")
best = [0] + [INF] * target # best[a] = fewest coins making a
for a in range(1, target + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1 # one coin on top of a solved amount
return -1 if best[target] == INF else best[target]
print(fewest([1, 5, 10], 27)) # 5
print(fewest([4, 6], 7)) # -1Your turn
Put the steps in the right order.
- Walk the amounts from 1 up to the target
- Return best[target], or -1 if it never improved
- For each coin that fits, try best[amount - coin] + 1 as a better answer
- Set best[0] to 0 and every other amount to infinity
Mini quiz
1 / 3