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。二、解题思路为什么用动态规划拿到这道题首先会想到暴力枚举——列举所有可能的硬币组合计算每个组合的硬币个数再取最小值。但这种方法的效率极低比如 amount100coins[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共 amount1 个状态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 的最少硬币数有两种选择不使用这枚硬币此时 dp[i] 保持原来的值无穷大或之前计算的最小值使用这枚硬币此时 dp[i] dp[i - coins[j]] 1dp[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的所有金额constLenamount1;// 2. 初始化dp数组所有元素为Infinitydp[0] 0constdpnewArray(Len).fill(Infinity);dp[0]0;// 3. 遍历所有金额从1到amount计算每个金额的最少硬币数for(leti1;iamount;i){// 4. 遍历所有硬币面额尝试用当前硬币凑成金额ifor(letj0;jcoins.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开始比如 amount11需要计算 dp[0] 到 dp[11]共12个元素所以长度是 amount1dp.fill(Infinity)初始化所有金额的最少硬币数为无穷大代表“暂时无法凑成”双重循环外层循环遍历金额从1到amount内层循环遍历硬币确保每个金额都尝试过所有可能的硬币组合return dp[amount] amount ? -1 : dp[amount]这里用 dp[amount] amount 判断是否无法凑成因为最多用 amount 枚1元硬币就能凑成 amount比如 amount11最多11枚1元如果 dp[amount] 大于 amount说明它还是初始的 Infinity无法凑成返回-1。六、测试用例验证帮你理解代码运行过程我们用之前的例子 coins [1,2,5]amount 11来模拟代码的运行过程看看 dp 数组是如何变化的初始化 dp [0, Infinity, Infinity, ..., Infinity]共12个元素i1金额1j0硬币11≤1dp[1] min(Infinity, dp[0]1) 011j1硬币221跳过j2硬币551跳过最终 dp[1] 1i2金额2j0硬币1dp[2] min(Infinity, dp[1]1) 2j1硬币22≤2dp[2] min(2, dp[0]1) 1j2硬币552跳过最终 dp[2] 1... 依次计算直到 i11j0硬币1dp[11] dp[10] 1j1硬币2dp[11] min(当前值, dp[9] 1)j2硬币5dp[11] min(当前值, dp[6] 1)最终 dp[11] 3dp[6] 11113所以代码返回 3和我们预期的结果一致。七、常见坑点与注意事项新手做这道题很容易踩坑这里总结几个关键注意点帮你避坑初始化 dp[0] 0 不能漏这是整个动态规划的基础没有这个条件所有子问题的计算都会出错硬币遍历的顺序不影响结果因为每种硬币可以无限使用无论先遍历哪枚硬币最终都会尝试所有可能的组合判断无法凑成的条件不能直接判断 dp[amount] Infinity因为在某些语言中Infinity 和其他值比较可能有异常用 dp[amount] amount 更稳妥比如 amount3最多3枚1元若 dp[3] 是 Infinity肯定大于3coins 数组可能为空题目中默认 coins 是有效的整数数组但如果 coins 为空且 amount0直接返回 -1代码中会因为循环不执行dp[amount] 还是 Infinity最终返回 -1无需额外处理。八、总结动态规划的解题套路通过这道题我们可以总结出动态规划的通用解题步骤后续遇到类似问题比如完全背包、爬楼梯等都可以套用定义 dp 数组明确 dp[i] 表示的含义核心步骤一定要想清楚初始化 dp 数组根据题目条件设置基础值比如 dp[0] 0和初始值比如 Infinity推导状态转移方程找到 dp[i] 和子问题 dp[i - k] 之间的关系遍历所有状态计算 dp 数组的值根据 dp 数组的最终值返回题目要求的结果。零钱兑换作为动态规划的入门题难度适中但能帮我们掌握核心思路。建议大家多动手调试代码模拟 dp 数组的变化过程真正理解每一步的含义后续再做类似的题目就会得心应手。