用python写给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。
时间: 2024-09-18 07:11:09 浏览: 70
在Python中,这个问题可以使用动态规划(Dynamic Programming)来解决。我们可以创建一个长度为`amount+1`的列表dp,其中`dp[i]`代表用硬币凑出金额i所需的最小硬币数。初始化所有dp值为无穷大(通常设置为sys.maxsize),除了dp[0]设为0,因为不需要硬币就能得到0元。
然后,遍历每个硬币面额`coins[j]`,对于每个`i`(从coins[j]到amount),更新`dp[i]`为`dp[i-coins[j]] + 1`,如果这个新值小于当前的dp[i],就更新它。这是因为我们考虑了使用一枚面额为`coins[j]`的硬币来凑`i`元的情况,如果这样做比之前更优,我们就接受这个方案。
最后,如果`dp[amount]`仍然是无穷大,说明无法用给定的硬币凑出指定的金额,返回-1;否则,返回`dp[amount]`就是所需的最少硬币数。
以下是Python代码实现:
```python
import sys
def coinChange(coins, amount):
dp = [sys.maxsize] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
if dp[i - coin] != sys.maxsize:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != sys.maxsize else -1
```
阅读全文