Find the smallest number of coins that make an amount.
What to build
A memoized recursive function where taking the largest coin first does not always work.
Requirements
- Read the coin values and the amount.
- Print the smallest number of coins that make exactly that amount.
- Print
-1if it cannot be done.
Input
Two lines: the coin values, then the amount.
Output
One number.
Constraints
There are from 1 to 10 coin values, from 1 to 100. The amount is from 0 to 500.
Example
Input:
1 5 10
18
Output:
5
Why it works
With coins of 1, 3 and 4, an amount of 6 is best made as 3 + 3. Taking the largest coin first gives 4 + 1 + 1, so every coin must be tried, and the memo keeps that affordable.
Examples
Example 1 · Input
1 5 10 18
Expected output
5
Example 2 · Input
2 3
Expected output
-1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
fewest(amount) is 1 + the smallest fewest(amount - coin) over all the coins that fit.
Hint 2
The base case is fewest(0) = 0.
Hint 3
Use infinity (float("inf")) for amounts that cannot be made.
Solution
Show one correct solution (try it yourself first)
from functools import lru_cache
coins = [int(x) for x in input().split()]
amount = int(input())
@lru_cache(maxsize=None)
def fewest(left):
if left == 0:
return 0
best = float("inf")
for coin in coins:
if coin <= left:
best = min(best, 1 + fewest(left - coin))
return best
answer = fewest(amount)
print(-1 if answer == float("inf") else answer)