动态规划算法凑硬币问题

动态规划算法可以用来解决凑硬币问题。该问题是给定不同面额的硬币和一个总金额，找出可以凑成总金额所需的最少硬币数量。下面是一个示例代码：

def coinChange(coins, amount):
    # 创建一个长度为amount+1的数组，用于存储每个金额所需的最少硬币数量
    dp = [float('inf')] * (amount + 1)
    # 金额为0时，所需的最少硬币数量为0
    dp[0] = 0

    # 遍历每个金额
    for i in range(1, amount + 1):
        # 遍历每个硬币面额
        for coin in coins:
            # 如果当前硬币面额小于等于当前金额
            if coin <= i:
                # 更新当前金额所需的最少硬币数量
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # 如果最终金额所需的最少硬币数量为无穷大，则表示无法凑出该金额
    if dp[amount] == float('inf'):
        return -1
    else:
        return dp[amount]

使用上述代码，可以通过传入硬币面额列表和目标金额来计算凑硬币问题的最少硬币数量。例如，假设硬币面额列表为[1, 2, 5]，目标金额为11，可以调用`coinChange([1, 2, 5], 11)`来计算最少硬币数量。