Review the AI
Fewest Coins
Is the greedy choice always right? Label the three solutions.Problem
min_coins(amount): with coins of 1, 3 and 4, what is the fewest coins that make amount? (0 ≤ amount ≤ 30)Solution A
1def min_coins(amount):
2 count = 0
3 for c in (4, 3, 1):
4 count += amount // c
5 amount %= c
6 return count
Solution B
1def min_coins(amount):
2 best = [0] + [amount + 1] * amount
3 for x in range(1, amount + 1):
4 for c in (1, 3, 4):
5 if c <= x:
6 best[x] = min(best[x], best[x - c] + 1)
7 return best[amount]
Solution C
1def min_coins(amount):
2 if amount == 0:
3 return 0
4 return 1 + min(min_coins(amount - c) for c in (1, 3, 4) if c <= amount)