给定一个正整数coin,表示总金额,给定一个整数数组coins,用元素表示现有的金额面值,计算并返回可以凑成总金额所需的最小硬币个数,(认为各种面值的金币个数是无限的) 如果给出的总金额无法兑换成现有的零钱,则返回-1。
时间: 2024-02-15 18:05:26 浏览: 82
这个问题可以通过动态规划求解。我们可以构建一个一维数组dp,其中dp[i]表示凑成总金额i所需的最小硬币数。初始时,我们将dp数组全部初始化为正无穷,除了dp[0]为0,表示凑成总金额为0所需的最小硬币数为0。然后,我们可以遍历每个金额i,对于每个金额i,我们遍历每个硬币面值j,如果硬币面值j小于等于金额i且dp[i - j]已经被计算过,那么我们更新dp[i]为dp[i - j] + 1和当前dp[i]中的较小值。最终,如果dp[coin]仍然为正无穷,则说明无法凑成总金额,返回-1,否则返回dp[coin]。
以下是Python的代码实现:
```
def coinChange(coins, coin):
dp = [float('inf')] * (coin + 1)
dp[0] = 0
for i in range(1, coin + 1):
for j in range(len(coins)):
if coins[j] <= i and dp[i - coins[j]] != float('inf'):
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
return dp[coin] if dp[coin] != float('inf') else -1
```
例如,当coins=[1, 2, 5],coin=11时,调用coinChange(coins, coin)将返回3,表示可以用3个硬币凑成总金额11(11=5+5+1);当coins=[2],coin=3时,调用coinChange(coins, coin)将返回-1,表示无法凑成总金额3。
阅读全文