用python写出最少硬币找零问题代码
时间: 2024-05-09 12:18:14 浏览: 14
当然,我会尽力回答你的问题。下面是用 Python 实现最少硬币找零问题的代码:
```python
def minCoins(coins, amount):
table = [float('inf')] * (amount+1)
table[0] = 0
for i in range(1, amount+1):
for j in range(len(coins)):
if coins[j] <= i:
sub_res = table[i-coins[j]]
if sub_res != float('inf') and sub_res+1 < table[i]:
table[i] = sub_res+1
if table[amount] == float('inf'):
return -1
else:
return table[amount]
coins = [1, 5, 10, 25]
amount = 30
print(minCoins(coins, amount))
```
其中,`coins` 数组表示硬币的面值,`amount` 变量表示要找的零钱数量。函数 `minCoins()` 采用动态规划的思想,通过逐步计算出从 1 到 `amount` 的最优解,最终返回 `amount` 需要的最少硬币数量。如果无法找到零钱组合来凑成 `amount`,则返回 -1。