动态规划经典问题找零钱

动态规划是一种常用的算法思想，用于解决一些具有重叠子问题和最优子结构性质的问题。其中，找零钱问题是动态规划的经典问题之一。

找零钱问题是指给定一定面额的硬币和一个目标金额，求解凑出目标金额所需的最少硬币数量。假设我们有面额为[1, 2, 5]的硬币，目标金额为11，我们可以使用动态规划来解决这个问题。

首先，我们定义一个数组dp，其中dp[i]表示凑出金额i所需的最少硬币数量。初始化dp数组为无穷大，除了dp为0，表示凑出金额0不需要任何硬币。

然后，我们从金额1开始逐步计算dp数组的值。对于每个金额i，我们遍历硬币的面额，假设当前硬币面额为coin，如果coin小于等于i，并且dp[i-coin]+1的值比dp[i]小，则更新dp[i]为dp[i-coin]+1。

最后，当计算完dp数组后，dp[amount]即为凑出目标金额所需的最少硬币数量。

下面是找零钱问题的动态规划解法的示例代码：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1