python硬币找零钱

在Python中，可以使用动态规划算法来解决硬币找零问题。动态规划是一种通过将问题分解为更小的子问题来解决复杂问题的方法。

以下是一个示例代码，用于找零钱并返回所需的最少硬币数量：

def coin_change(coins, amount):
    # 创建一个列表来保存每个金额所需的最少硬币数量
    dp = [float('inf')] * (amount + 1)
    # 金额为0时，所需的最少硬币数量为0
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                # 更新最少硬币数量
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 如果最少硬币数量仍然为初始值，则表示无法凑出该金额
    if dp[amount] == float('inf'):
        return -1
    else:
        return dp[amount]

使用示例：

coins = [1, 2, 5]  # 可用的硬币面额
amount = 11  # 需要找零的金额

result = coin_change(coins, amount)
print(f"需要的最少硬币数量为：{result}")

输出结果为：

需要的最少硬币数量为：3

这表示需要3枚硬币才能凑出11元。