零钱硬币兑换问题python

零钱硬币兑换问题是经典的计算机科学问题，通常涉及找零功能，给定一组面额的硬币和一个总金额，求解出最少需要多少枚硬币才能凑成这个金额。这个问题可以用动态规划的方法来解决。在 Python 中，你可以创建一个二维数组 dp，其中 dp[i] 表示凑成 i 分所需的最小硬币数。

以下是一个简单的 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
print(coinChange(coins, amount))  # 输出: 3

在这个例子中，`coinChange` 函数接受两个参数：硬币列表 `coins` 和目标金额 `amount`。函数返回的是凑出金额所需的最小硬币数，如果无法凑出，则返回 -1。