好的，我们接下来讲解 LeetCode 第 322 题：零钱兑换（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

解题思路（动态规划）

这是一个经典的 完全背包问题，我们可以使用 动态规划（Dynamic Programming） 来解决。核心思想是：将大问题分解为小问题，逐步求解。

第一步：定义状态

我们定义一个数组 dp，其中：

• dp[i] 表示凑成总金额 i 所需的最少硬币个数。
• 我们的目标是求 dp[amount]。

第二步：初始化状态

• dp[0] = 0：凑成总金额 0 需要 0 个硬币。
• 对于其他金额 i（从 1 到 amount），我们初始化为一个很大的数（比如 amount + 1 或 Infinity），表示暂时无法凑出。

第三步：状态转移方程

对于每个金额 i（从 1 到 amount），我们遍历每一种硬币 coin：

• 如果 coin <= i（表示这枚硬币可以用于凑金额 i），那么：

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

• 解释：dp[i - coin] + 1 表示使用这枚硬币后，剩余金额 i - coin 的最少硬币数加上当前这枚硬币。

第四步：填表计算

我们从小到大计算每个 dp[i]，确保在计算 dp[i] 时，dp[i - coin] 已经计算过。

第五步：返回结果

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

详细推导（以示例 1 为例）

输入： coins = [1, 2, 5], amount = 11

1. 初始化 dp 数组：

   • dp[0] = 0
   • dp[1] 到 dp[11] 初始化为 12（因为 amount + 1 = 12）

2. 计算 dp[1]：

   • 可用硬币：1
   • dp[1] = min(dp[1], dp[1 - 1] + 1) = min(12, dp[0] + 1) = min(12, 1) = 1

3. 计算 dp[2]：

   • 硬币 1：dp[2] = min(12, dp[1] + 1) = min(12, 2) = 2
   • 硬币 2：dp[2] = min(2, dp[0] + 1) = min(2, 1) = 1
   • 所以 dp[2] = 1

4. 计算 dp[3]：

   • 硬币 1：dp[3] = min(12, dp[2] + 1) = min(12, 2) = 2
   • 硬币 2：dp[3] = min(2, dp[1] + 1) = min(2, 2) = 2
   • 所以 dp[3] = 2

5. 继续计算直到 dp[11]：

   • dp[11] = min(dp[11], dp[11 - 1] + 1) = min(12, dp[10] + 1)
   • dp[11] = min(12, dp[9] + 2)（使用硬币 2）
   • dp[11] = min(12, dp[6] + 1)（使用硬币 5）
   • 最终 dp[11] = 3（由 5 + 5 + 1 组成）

复杂度分析

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

总结

这道题的关键在于：

1. 识别出这是 完全背包 问题。
2. 定义 dp[i] 为凑出金额 i 的最少硬币数。
3. 通过遍历硬币和金额，逐步更新 dp 数组。
4. 注意初始化 dp[0] = 0 和无法凑出时的返回值为 -1。

这种方法保证了我们能够高效地找到最优解。