LeetCode 322. 零钱兑换：动态规划入门实战-程序员充电站

作为动态规划领域的经典入门题，LeetCode 322. 零钱兑换不仅考察对「最优子结构」的理解，更能帮我们掌握动态规划的核心解题思路——把复杂问题拆解成可重复解决的子问题，通过存储子问题答案避免重复计算。今天就带大家从头到尾吃透这道题，从问题分析到代码实现，每一步都讲透，新手也能轻松跟上。

一、题目解读：读懂问题核心

题目很简洁，但细节不能漏，我们先把关键信息提炼出来：

输入：一个整数数组 coins（表示不同面额的硬币，比如 [1,2,5]），一个整数 amount（表示需要凑成的总金额，比如 11）；
输出：凑成总金额所需的最少硬币个数；如果无法凑成，返回 -1；
关键条件：每种硬币的数量是无限的（这是「完全背包问题」的典型特征，和0-1背包的“每种物品只能用一次”区分开）。

举个例子帮助理解：

若 coins = [1,2,5]，amount = 11，最优解是 2枚5元 + 1枚1元，共3枚硬币，所以返回3；

若 coins = [2]，amount = 3，没有任何组合能凑成3，返回 -1。

二、解题思路：为什么用动态规划？

拿到这道题，首先会想到暴力枚举——列举所有可能的硬币组合，计算每个组合的硬币个数，再取最小值。但这种方法的效率极低，比如 amount=100，coins=[1,2,5]，枚举的组合数会呈指数级增长，根本无法应对较大的测试用例。

这时候就需要动态规划登场了。动态规划的核心思想是「重叠子问题」和「最优子结构」：

重叠子问题：凑成金额 i 的最少硬币数，依赖于凑成金额 i - coins[j] 的最少硬币数（比如凑11元，依赖于凑10元、9元、6元的最少硬币数），这些子问题会被重复计算，我们可以用一个数组存储子问题的答案，避免重复运算；
最优子结构：凑成金额 i 的最少硬币数，一定是所有「i - coins[j] 的最少硬币数 + 1」中的最小值（加1是因为要加上当前使用的这枚 coins[j] 硬币）。

基于这个思路，我们可以设计一个动态规划数组 dp，来存储每个金额对应的最少硬币数。

三、动态规划数组设计与初始化

1. dp数组的定义

定义 dp[i] 表示：凑成总金额 i 所需的最少硬币个数。

比如 dp[0] 表示凑成金额0所需的硬币数，显然是0（不需要任何硬币）；dp[1] 表示凑成金额1所需的最少硬币数，若有1元硬币则为1，若无则为无法凑成。

2. 初始化细节

我们需要初始化一个长度为 amount + 1 的 dp 数组（因为金额从0到amount，共 amount+1 个状态）：

dp[0] = 0：这是基础条件，凑成金额0不需要任何硬币；
其余 dp[i] 初始化为 Infinity（无穷大）：因为一开始我们不知道能否凑成金额 i，用无穷大表示“暂时无法凑成”，后续如果能凑成，再更新为具体的最小值。

这里有个小细节：为什么用 Infinity 而不是其他值？因为我们要取最小值，初始化为无穷大，才能保证后续的 min 运算能正确更新 dp[i]（如果初始化为其他较大值，可能会影响结果，但 Infinity 是最直观、最安全的选择）。

四、状态转移方程推导

有了 dp 数组的定义和初始化，接下来就是核心的状态转移过程——如何从子问题的答案推出当前问题的答案。

对于每个金额 i（从1到amount），我们遍历所有硬币面额 coins[j]：

如果 coins[j] > i：说明这枚硬币的面额比当前金额还大，无法使用，跳过；
如果 coins[j] ≤ i：说明这枚硬币可以使用，此时凑成金额 i 的最少硬币数，有两种选择：
1. 不使用这枚硬币：此时 dp[i] 保持原来的值（无穷大或之前计算的最小值）；
2. 使用这枚硬币：此时 dp[i] = dp[i - coins[j]] + 1（dp[i - coins[j]] 是凑成 i - coins[j] 的最少硬币数，加1是因为加上当前这枚硬币）。

因此，状态转移方程为：

dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)（当 coins[j] ≤ i 时）

五、完整代码解析（逐行拆解）

给出的代码已经是最优解（时间复杂度 O(amount × len(coins))，空间复杂度 O(amount)），我们逐行拆解，搞懂每一步的作用：

functioncoinChange(coins:number[],amount:number):number{// 1. 定义dp数组的长度：amount + 1（覆盖0到amount的所有金额）constLen=amount+1;// 2. 初始化dp数组：所有元素为Infinity，dp[0] = 0constdp=newArray(Len).fill(Infinity);dp[0]=0;// 3. 遍历所有金额（从1到amount），计算每个金额的最少硬币数for(leti=1;i<=amount;i++){// 4. 遍历所有硬币面额，尝试用当前硬币凑成金额ifor(letj=0;j<coins.length;j++){// 5. 只有当硬币面额≤当前金额时，才能使用这枚硬币if(coins[j]<=i){// 6. 状态转移：取“不使用当前硬币”和“使用当前硬币”的最小值dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);}}}// 7. 最终判断：如果dp[amount]还是Infinity，说明无法凑成，返回-1；否则返回dp[amount]returndp[amount]>amount?-1:dp[amount];};

关键代码细节说明：

Len = amount + 1：因为金额从0开始，比如 amount=11，需要计算 dp[0] 到 dp[11]，共12个元素，所以长度是 amount+1；
dp.fill(Infinity)：初始化所有金额的最少硬币数为无穷大，代表“暂时无法凑成”；
双重循环：外层循环遍历金额（从1到amount），内层循环遍历硬币，确保每个金额都尝试过所有可能的硬币组合；
return dp[amount] > amount ? -1 : dp[amount]：这里用 dp[amount] > amount 判断是否无法凑成，因为最多用 amount 枚1元硬币就能凑成 amount（比如 amount=11，最多11枚1元），如果 dp[amount] 大于 amount，说明它还是初始的 Infinity，无法凑成，返回-1。

六、测试用例验证（帮你理解代码运行过程）

我们用之前的例子 coins = [1,2,5]，amount = 11，来模拟代码的运行过程，看看 dp 数组是如何变化的：

初始化 dp = [0, Infinity, Infinity, ..., Infinity]（共12个元素）；
i=1（金额1）：
- j=0（硬币1）：1≤1，dp[1] = min(Infinity, dp[0]+1) = 0+1=1；
- j=1（硬币2）：2>1，跳过；j=2（硬币5）：5>1，跳过；最终 dp[1] = 1；
i=2（金额2）：
- j=0（硬币1）：dp[2] = min(Infinity, dp[1]+1) = 2；
- j=1（硬币2）：2≤2，dp[2] = min(2, dp[0]+1) = 1；
- j=2（硬币5）：5>2，跳过；最终 dp[2] = 1；
... 依次计算，直到 i=11：
- j=0（硬币1）：dp[11] = dp[10] + 1；
- j=1（硬币2）：dp[11] = min(当前值, dp[9] + 1)；
- j=2（硬币5）：dp[11] = min(当前值, dp[6] + 1)；
- 最终 dp[11] = 3（dp[6] = 1，1+1+1=3）；

所以代码返回 3，和我们预期的结果一致。

七、常见坑点与注意事项

新手做这道题很容易踩坑，这里总结几个关键注意点，帮你避坑：

初始化 dp[0] = 0 不能漏：这是整个动态规划的基础，没有这个条件，所有子问题的计算都会出错；
硬币遍历的顺序不影响结果：因为每种硬币可以无限使用，无论先遍历哪枚硬币，最终都会尝试所有可能的组合；
判断无法凑成的条件：不能直接判断 dp[amount] === Infinity，因为在某些语言中，Infinity 和其他值比较可能有异常，用 dp[amount] > amount 更稳妥（比如 amount=3，最多3枚1元，若 dp[3] 是 Infinity，肯定大于3）；
coins 数组可能为空？题目中默认 coins 是有效的整数数组，但如果 coins 为空且 amount>0，直接返回 -1（代码中会因为循环不执行，dp[amount] 还是 Infinity，最终返回 -1，无需额外处理）。