硬币问题动态规划
时间: 2023-06-28 20:12:25 浏览: 53
硬币问题是一个著名的动态规划问题,其描述为:给定不同面额的硬币和一个总金额,编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
例如,假设有三种面值的硬币,分别为1元、2元、5元,需要凑成11元,那么最少需要的硬币数为3枚(5元+5元+1元)。
解决这个问题的一种常见方法是使用动态规划。具体来说,我们定义一个长度为amount+1的数组dp,其中dp[i]表示凑成金额i所需的最少硬币个数。初始时,dp[0]=0,表示凑成金额0不需要任何硬币。对于每个金额i,我们遍历所有的硬币面值j,如果j<=i,则可以使用一枚面值为j的硬币,将问题转化为求解凑成金额i-j所需的最少硬币个数,即dp[i-j]+1。我们只需要选择所有方案中最小的那个作为dp[i]的值即可。
最终,dp[amount]就是所求的答案。
下面是一个使用Python实现的动态规划算法:
```python
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for j in coins:
if j <= i:
dp[i] = min(dp[i], dp[i - j] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
```
在上面的代码中,coins表示硬币面值列表,amount表示需要凑成的金额。我们首先初始化dp数组,将所有元素设置为正无穷,然后将dp[0]设为0。接下来,我们遍历所有的金额i,对于每个金额i,再遍历所有的硬币面值j,如果j<=i,则更新dp[i]的值为dp[i-j]+1和dp[i]中的较小值。最后返回dp[amount]的值,如果它仍然是正无穷,则说明无法凑成金额amount,返回-1即可。