有一个正整数数组coins={2,5,7},代表不同的硬币面额,还有一个总金额为40,求出要凑成这个金额所需要的最少硬币数量。(硬币数量无限)
时间: 2024-02-26 14:59:02 浏览: 50
算法最少硬币问题题目
这是一个经典的动态规划问题,可以使用动态规划算法来解决。
首先定义一个数组dp,其中dp[i]表示凑成金额为i所需要的最少硬币数量。初始化dp[0]为0,其他元素初始化为正无穷大。
接下来,对于每个金额i,遍历硬币面额coins[j],如果当前硬币面额小于等于i,那么可以选择使用这个硬币,此时凑成金额i所需要的最少硬币数量为dp[i-coins[j]]+1和当前dp[i]中的较小值。
最终,dp[40]就是凑成40所需要的最少硬币数量。
以下是Python代码实现:
```python
coins = [2, 5, 7]
target = 40
dp = [float('inf')] * (target + 1)
dp[0] = 0
for i in range(1, target + 1):
for j in range(len(coins)):
if coins[j] <= i:
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
print(dp[target])
```
输出结果为5,即凑成40所需要的最少硬币数量为5。
阅读全文