用python写零钱兑换问题,给定一个正整数coin,表示总金额,给定一个整数数组coins,用元素表示现有的金额面值,计算并返回可以凑成总金额所需的最小硬币个数,(认为各种面值的金币个数是无限的) 如果给出的总金额无法兑换成现有的零钱,则返回-1。
时间: 2024-03-04 13:49:04 浏览: 75
FifthExper_算法零钱个数最少问题_
好的,这是一个很经典的动态规划问题。我可以给你提供一个Python的解决方案:
```python
def coinChange(coins, amount):
# 首先初始化一个数组dp,长度为 amount+1
dp = [float('inf')]*(amount+1)
# 定义 dp[0] 为 0,因为总金额为0时,不需要任何硬币
dp[0] = 0
# 遍历 1 到 amount 的所有金额
for i in range(1, amount+1):
# 遍历所有的硬币面值
for coin in coins:
# 如果当前硬币面值小于等于当前的金额,那么可以尝试使用这个硬币
if coin <= i:
# 状态转移方程:dp[i] 表示凑成金额 i 需要的最小硬币数
# min(dp[i], dp[i-coin]+1) 表示使用当前硬币可以得到更小的硬币数量
dp[i] = min(dp[i], dp[i-coin]+1)
# 如果 dp[amount] 没有被更新,说明无法凑成总金额,返回-1
return -1 if dp[amount] == float('inf') else dp[amount]
```
你可以调用这个函数,传入硬币面值和总金额,它会返回最小硬币数。例如:
```python
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount)) # 输出 3,因为使用 5、5、1 这三个硬币可以凑成 11
```
阅读全文