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

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

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

输入：coins = [2], amount = 3
输出：-1
解释：无法用面额2的硬币凑出3。

解题过程循序渐进讲解

步骤1：理解问题与目标
这是一个经典的“完全背包”类问题，属于动态规划中的“最值”型。
我们需要用最少数量的硬币凑出总金额 amount，每种硬币可以无限使用。
动态规划适合解决这类问题，因为：

• 问题可以分解为子问题：凑出金额 i 的最少硬币数，可以由更小的金额 i - coin 推导而来。
• 存在重叠子问题：凑金额 i 时，会多次用到更小子问题的解。

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

• 最终目标是求 dp[amount]。
• 初始时，dp[0] = 0，因为凑出金额0不需要任何硬币。
• 对于无法凑出的金额，我们可以用一个大数（如 amount + 1 或 INT_MAX）表示“无穷大”，最后判断是否被更新。

步骤3：状态转移方程
对于每个金额 i（从1到 amount），我们尝试使用每一种硬币 coin：

• 如果 i >= coin，说明可以用这枚硬币，那么凑出金额 i 的一种可能方式是：先用这枚硬币，再用最少的硬币凑出剩下的金额 i - coin，即 1 + dp[i - coin]。
• 我们枚举所有可用的硬币，取最小值：

\[ dp[i] = \min_{coin \in coins} \{ dp[i - coin] + 1 \} \]

前提是 i >= coin 且 dp[i - coin] 是可以凑出的（不是无穷大）。

举例：coins = [1, 2, 5], amount = 11

• 计算 dp[11] 时，会考虑：
  • 用1元硬币：1 + dp[10]
  • 用2元硬币：1 + dp[9]
  • 用5元硬币：1 + dp[6]
    然后取三者最小值。

步骤4：初始化与边界处理

• dp[0] = 0
• 对于其他 i（1 ≤ i ≤ amount），先初始化为一个很大的数，比如 amount + 1（因为最多用 amount 枚1元硬币，所以 amount + 1 可视为不可达）。
• 如果最终 dp[amount] 仍为这个很大的数，说明无法凑出，返回 -1。

步骤5：计算顺序
因为 dp[i] 依赖于更小的 dp[i - coin]，所以我们应该从小到大计算 dp 数组。
具体实现时，外层循环遍历金额 i 从1到 amount，内层循环遍历所有硬币，尝试更新 dp[i]。

步骤6：示例推演
以 coins = [1, 2, 5], amount = 11 为例：

初始化 dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] （用12表示初始无穷大）

i = 1:

• coin=1: dp[1] = min(dp[1], 1+dp[0]) = 1
  所以 dp[1]=1

i = 2:

• coin=1: dp[2] = min(12, 1+dp[1])=2
• coin=2: dp[2] = min(2, 1+dp[0])=1
  所以 dp[2]=1

i = 3:

• coin=1: dp[3]=1+dp[2]=2
• coin=2: dp[3]=1+dp[1]=2
  所以 dp[3]=2

i = 4:

• coin=1: 1+dp[3]=3
• coin=2: 1+dp[2]=2
  所以 dp[4]=2

i = 5:

• coin=1: 1+dp[4]=3
• coin=2: 1+dp[3]=3
• coin=5: 1+dp[0]=1
  所以 dp[5]=1

继续计算到 i=11：
dp[11] = min(1+dp[10], 1+dp[9], 1+dp[6])

• dp[10] = 2（5+5）
• dp[9] = 3（5+2+2）
• dp[6] = 2（5+1）
  所以 dp[11] = min(3, 4, 3) = 3

结果：3

步骤7：算法复杂度

• 时间复杂度：O(amount × n)，n 是硬币种类数。
• 空间复杂度：O(amount)，用于存储 dp 数组。

步骤8：代码框架（C++风格）

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

步骤9：关键点与常见错误

1. 初始值不要设为0（除了 dp[0]），否则 min 比较会出错。
2. 内层循环遍历硬币，而不是遍历1到i的所有数，因为硬币是给定的，不是所有整数都能用。
3. 如果没有任何硬币能组成金额，dp[amount] 会保持初始大数，返回 -1。
4. 这是一种“完全背包”问题的“最小值”版本，与“组合数”问题（如凑金额的组合数）的状态转移不同（后者是累加方案数）。

总结
这个问题的核心是将大问题（凑 amount）分解为小问题（凑 i），利用子问题的最优解构造当前解。
通过自底向上的动态规划，避免了重复计算，高效地得到了最少硬币数。