动态规划解决硬币找零问题（最少硬币数）

题目描述
给定不同面额的硬币数组 coins 和一个总金额 amount。计算凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

示例

• 输入：coins = [1, 2, 5], amount = 11
  输出：3（解释：5 + 5 + 1 = 11）
• 输入：coins = [2], amount = 3
  输出：-1（无法用面额2的硬币凑出3）

解题思路
这是一个典型的动态规划（DP）问题，类似于完全背包。核心思路是构建一个DP数组 dp，其中 dp[i] 表示凑出金额 i 所需的最少硬币数量。初始时，dp[0] = 0（金额0不需要硬币），其他位置设为一个大数（如 amount + 1 或 float('inf')）。然后遍历每个金额，对于每个金额，尝试使用每个硬币来更新最小硬币数。

详细解题步骤

步骤1：定义状态
设 dp[i] 表示凑出金额 i 所需的最少硬币个数。

步骤2：确定初始状态

• dp[0] = 0，金额为0时不需要硬币。
• 对于 i > 0，初始设为 amount + 1（因为最多用 amount 个1元硬币，amount + 1 表示不可达状态）。

步骤3：状态转移方程
对于每个金额 i 从 1 到 amount，遍历每个硬币 coin：
如果 coin <= i，说明可以使用这个硬币，则更新：

dp[i] = min(dp[i], dp[i - coin] + 1)

含义是：凑出金额 i 的最少硬币数，可以是“凑出金额 i - coin 所需硬币数 + 当前这枚硬币”。

步骤4：计算顺序
外层循环遍历金额 i 从 1 到 amount，内层循环遍历每个硬币。注意：内外层可以交换，但遍历硬币在外层时含义稍有不同（完全背包的两种遍历顺序）。

步骤5：最终结果
如果 dp[amount] 仍为初始值 amount + 1，说明无法凑出，返回 -1；否则返回 dp[amount]。

代码实现（Python）

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)  # 初始化
    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)
    return -1 if dp[amount] > amount else dp[amount]

实例推演

以 coins = [1, 2, 5], amount = 11 为例：
初始化：dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

• i = 1：
  coin=1 → dp[1] = min(12, dp[0]+1=1) → 1
  其他coin > 1跳过
  最终dp[1] = 1
• i = 2：
  coin=1 → dp[2] = min(12, dp[1]+1=2) → 2
  coin=2 → dp[2] = min(2, dp[0]+1=1) → 1
  dp[2] = 1
• ... 逐步计算 ...
• i = 11：
  coin=1 → dp[11] = min(12, dp[10]+1) 此时dp[10]之前已算得为2 → 3
  coin=2 → dp[11] = min(3, dp[9]+1=3) → 3
  coin=5 → dp[11] = min(3, dp[6]+1=3) → 3

最终 dp[11] = 3，返回 3。

复杂度分析

• 时间复杂度：O(amount × n)，其中 n 是硬币种数。
• 空间复杂度：O(amount)。

关键点总结

1. 初始化 dp[0] = 0，其他为较大值。
2. 状态转移时注意硬币面额不能大于当前金额。
3. 返回时判断是否可达。