巧凑硬币 python

巧凑硬币是一个问题，目的是找到一种最高效的方法来组合给定数量的硬币，使其总值等于指定的数额。使用Python可以通过动态规划算法来解决这个问题。可以创建一个数组dp，其中dp[i]表示构成数额为i的硬币组合的方法数。然后可以使用循环来计算dp的值，通过迭代计算dp[i] = dp[i] + dp[i-coin]，其中coin是可用的硬币面额。最后，dp[target]的值即为所需的结果。

以下是巧凑硬币问题的Python代码示例：

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
result = coinChange(coins, amount)
print(result)  # 输出: 3，表示需要3枚硬币来凑齐总值为11的金额