python动态规划找零钱代码

在Python中，动态规划是一种解决问题的有效算法策略，特别适用于求解最优化问题，如找零钱问题。这是一个典型的背包问题，假设有一个数组`coins`表示不同面额的硬币，我们需要找到最少的硬币组合来达到给定的目标金额`target`。

下面是一个简单的动态规划解决方案：

def coinChange(coins, target):
    dp = [float('inf')] * (target + 1)  # 初始化dp数组，所有值设为无穷大，除了0
    dp[0] = 0  # 当目标金额为0时，不需要硬币

    # 使用动态规划填充dp数组
    for i in range(1, target + 1):  
        for coin in coins:
            if i >= coin:  # 只有当目标大于等于当前硬币面额时才考虑使用
                dp[i] = min(dp[i], dp[i - coin] + 1)  # 更新最小硬币数

    return dp[target] if dp[target] != float('inf') else -1  # 如果找不到解，则返回-1

# 示例
coins = [1, 2, 5]
target = 11
print(coinChange(coins, target))  # 输出：3

在这个代码中，`dp[i]` 表示达到金额 `i` 最小需要的硬币数目。我们从`target`开始向下遍历，对于每个金额 `i`，检查是否可以使用当前的硬币 `coin`，如果可以，就更新 `dp[i]` 为当前所需的硬币数加一，取其与之前计算结果的最小值。