Python凑硬币问题

在本文中，我们将详细介绍Python中的凑硬币问题。

一、问题介绍

凑硬币问题是一个经典的动态规划问题，其目标是找到使用最少的硬币数量来凑成指定金额的零钱。例如，给定面值为[1, 2, 5]的硬币和金额11，我们要找到最少需要的硬币数量。

coins = [1, 2, 5]
amount = 11

二、解决方案

为了解决凑硬币问题，我们可以使用动态规划算法。首先，我们创建一个长度为amount+1的列表dp，并将其所有元素初始化为一个足够大的值（例如，amount+1）。列表dp中的每个元素表示凑齐对应金额所需的最小硬币数。

dp = [float('inf')] * (amount + 1)
dp[0] = 0

然后，我们通过遍历所有硬币面值和所有金额，更新dp列表的值。对于每个金额，我们遍历所有硬币面值，并尝试使用当前硬币凑成该金额。如果使用当前硬币所需的硬币数量小于当前最小硬币数，我们就更新dp列表中的值。

for coin in coins:
    for i in range(coin, amount + 1):
        dp[i] = min(dp[i], dp[i - coin] + 1)

最后，我们返回dp列表中amount位置的值，即为凑齐指定金额所需的最小硬币数量。

return dp[amount] if dp[amount] != float('inf') else -1

三、代码示例

下面是一个完整的示例代码：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))

以上代码将输出最少需要的硬币数量。

四、总结

在本文中，我们介绍了Python中凑硬币问题的解决方案。通过使用动态规划算法，我们可以求解最少需要的硬币数量，从而实现凑齐指定金额的目标。