线性动态规划：零钱兑换（Coin Change）

题目描述

你有一个整数数组 coins 表示不同面额的硬币，每种硬币的数量无限。另有一个整数 amount 表示总金额。
请计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

解题思路

这是一个典型的 完全背包问题，但这里我们求的是“最少物品数”而不是最大价值。
设 dp[i] 表示凑出金额 i 所需的最少硬币数。
目标是求 dp[amount]。

逐步分析

1. 定义状态

dp[i] = 凑出金额 i 所需的最少硬币数。
i 从 0 到 amount。

2. 初始条件

• dp[0] = 0：凑出金额 0 需要 0 个硬币。
• 其他 dp[i] 初始化为一个很大的数（比如 amount + 1 或 float('inf')），表示暂时无法凑出。

3. 状态转移

对于每个金额 i 从 1 到 amount，我们尝试用每种硬币 coin 去凑：
如果 i >= coin，说明可以用这枚硬币，那么凑出金额 i 的一种方式是：先凑出 i - coin，然后加上这枚硬币。
所以：

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

注意：硬币可以重复使用，这是“完全背包”的特点，在代码实现时，循环的顺序很重要。

4. 完全背包的循环顺序

因为每种硬币数量无限，在遍历 i 从 1 到 amount 时，对于每个 coin 应该放在内层循环，并且内层循环中 i 从小到大遍历，这样才能保证每个硬币可以重复使用。

另一种理解：
外层循环遍历硬币，内层循环遍历金额 i 从 coin 到 amount，这样可以保证每种硬币可以多次使用。
两种循环顺序都是对的，但常用的是外层遍历硬币，内层遍历金额，这样逻辑更直观。

5. 最终结果

如果 dp[amount] 仍为初始的大数，说明无法凑出，返回 -1，否则返回 dp[amount]。

详细步骤示例

coins = [1, 2, 5], amount = 11

初始化：
dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

外层遍历硬币 coin = 1：

• i 从 1 到 11：
  • i=1: dp[1] = min(dp[1], dp[0]+1) = 1
  • i=2: dp[2] = min(dp[2], dp[1]+1) = 2
  • ... 一直到 i=11: dp[11] = 11

此时 dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

外层遍历硬币 coin = 2：

• i 从 2 到 11：
  • i=2: dp[2] = min(dp[2], dp[0]+1) = 1
  • i=3: dp[3] = min(dp[3], dp[1]+1) = 2
  • i=4: dp[4] = min(dp[4], dp[2]+1) = 2
  • i=5: dp[5] = min(dp[5], dp[3]+1) = 3
  • i=6: dp[6] = min(dp[6], dp[4]+1) = 3
  • i=7: dp[7] = min(dp[7], dp[5]+1) = 4
  • i=8: dp[8] = min(dp[8], dp[6]+1) = 4
  • i=9: dp[9] = min(dp[9], dp[7]+1) = 5
  • i=10: dp[10] = min(dp[10], dp[8]+1) = 5
  • i=11: dp[11] = min(dp[11], dp[9]+1) = 6

此时 dp[11] 从 11 减少到 6。

外层遍历硬币 coin = 5：

• i 从 5 到 11：
  • i=5: dp[5] = min(3, dp[0]+1) = 1
  • i=6: dp[6] = min(3, dp[1]+1) = 2
  • i=7: dp[7] = min(4, dp[2]+1) = 2
  • i=8: dp[8] = min(4, dp[3]+1) = 3
  • i=9: dp[9] = min(5, dp[4]+1) = 3
  • i=10: dp[10] = min(5, dp[5]+1) = 2
  • i=11: dp[11] = min(6, dp[6]+1) = 3

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

代码实现（Python）

def coinChange(coins, amount):
    INF = amount + 1
    dp = [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] != INF else -1

复杂度分析

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

关键点总结

1. 这是完全背包求最少物品数的问题。
2. 状态定义：dp[i] 是凑出金额 i 的最少硬币数。
3. 初始条件：dp[0] = 0，其他为无穷大。
4. 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)。
5. 循环顺序：外层遍历硬币，内层遍历金额从小到大，保证硬币可重复使用。
6. 如果最终 dp[amount] 为无穷大，返回 -1。

这个算法是解决“最少硬币数”问题的标准动态规划解法，在面试和竞赛中经常出现。