3.零钱兑换 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。用python编写
时间: 2024-09-13 20:02:56 浏览: 12
在Python中,我们可以使用动态规划(Dynamic Programming)的思想来解决这个问题,即采用贪心策略,从最小面额的硬币开始尝试,看是否能用这个面额的硬币凑出总金额的一部分,然后再继续尝试更大的面额。直到总金额减去当前硬币面额的倍数大于等于0,就说明无法再增加更多的这种面额硬币了。我们将这个过程记录下来,最终返回的是从最大面额到最小面额所需硬币的最短路径数目。
这是一个典型的“背包”问题,我们可以创建一个大小为amount+1的数组dp,其中dp[i]表示凑出i单位金额所需的最少硬币数。初始状态dp[0]=0,因为不需要硬币就可以得到0元。然后遍历硬币数组,对于每一个硬币,更新dp数组:
```python
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1) # 初始化dp数组,所有值设为无穷大
dp[0] = 0 # 无需硬币就可以得到0元,dp[0]为0
for coin in coins:
for i in range(coin, amount + 1): # 尝试用每种面额的硬币替换dp[i]
dp[i] = min(dp[i], dp[i - coin] + 1) # 更新dp[i]
# 若存在可行解,则返回最少硬币数,否则返回-1
return dp[-1] if dp[amount] < float('inf') else -1
# 示例:
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount)) # 输出:3
```