动态规划经典问题：零钱兑换与组合总和解法对比

1. 动态规划经典问题解析零钱兑换与组合总和今天我们来深入探讨两个经典的动态规划问题518. 零钱兑换 II和377. 组合总和 Ⅳ。这两个问题在算法面试中频繁出现也是理解动态规划思想的重要案例。我将在本文中分享我对这两个问题的完整解题思路、代码实现以及一些容易被忽略的细节。1.1 问题背景与区别零钱兑换 II518题要求计算用给定面额的硬币凑成指定金额的组合数这里顺序不同的组合视为相同即12和21算作同一种情况。而组合总和 Ⅳ377题虽然题目描述类似但顺序不同的序列被视为不同的组合。这个关键区别导致了完全不同的解题思路零钱兑换 II完全背包问题关注的是组合数组合总和 Ⅳ更接近爬楼梯问题关注的是排列数重要提示很多同学容易混淆这两个问题的解法关键在于理解题目是否考虑顺序。在实际面试中务必先确认清楚题目要求。2. 零钱兑换 II 的完全背包解法2.1 问题重述给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数。假设每种面额的硬币数量无限。示例 输入amount 5, coins [1, 2, 5] 输出4 解释有四种方式可以凑成总金额 55 5221 52111 5111112.2 动态规划思路这是一个典型的完全背包问题我们可以使用动态规划来解决定义dp数组dp[j]表示凑成金额j的组合数初始化dp[0] 1凑成金额0有一种方式什么都不选状态转移方程dp[j] dp[j - coin]遍历顺序外层遍历硬币内层遍历金额这是关键def change(amount, coins): dp [0] * (amount 1) dp[0] 1 for coin in coins: for j in range(coin, amount 1): dp[j] dp[j - coin] return dp[amount]2.3 为什么遍历顺序很重要这里的外层循环硬币、内层循环金额的顺序至关重要。这种顺序确保了我们在考虑组合时不会重复计算顺序不同的情况即12和21被视为同一种组合。如果交换循环顺序就变成了考虑排列数的问题会得到错误的结果。这是很多初学者容易犯的错误。3. 组合总和 Ⅳ 的排列数解法3.1 问题重述给定一个由不同整数组成的数组nums和一个目标整数target从nums中找出并返回总和为target的元素组合的个数。顺序不同的序列被视为不同的组合。示例 输入nums [1,2,3], target 4 输出7 解释 所有可能的组合为 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)3.2 动态规划思路这个问题需要考虑顺序因此解法与零钱兑换II不同定义dp数组dp[i]表示凑成目标i的组合数初始化dp[0] 1状态转移方程dp[i] dp[i - num] for num in nums if i num遍历顺序外层遍历目标内层遍历数字def combinationSum4(nums, target): dp [0] * (target 1) dp[0] 1 for i in range(1, target 1): for num in nums: if i num: dp[i] dp[i - num] return dp[target]3.3 与爬楼梯问题的联系这个问题实际上可以看作是爬楼梯问题的泛化版本。在爬楼梯问题中每次可以爬1或2阶楼梯而这里每次可以爬nums中的任意一个数字的阶数。理解这种联系有助于我们更好地把握这类问题的本质。4. 关键区别与常见错误4.1 两种问题的对比特性零钱兑换 II (518)组合总和 Ⅳ (377)是否考虑顺序否是循环顺序物品外层容量内层容量外层物品内层实际应用货币兑换序列生成类似问题完全背包爬楼梯4.2 常见错误与调试技巧混淆循环顺序这是最常见的错误。记住组合问题不考虑顺序物品在外层循环排列问题考虑顺序容量在外层循环初始化错误总是忘记dp[0] 1的初始化数组越界在内层循环中忘记检查i num的条件整数溢出组合总和Ⅳ的测试用例可能会有很大的结果在某些语言中需要考虑使用更大的整数类型调试技巧对于动态规划问题建议打印出dp数组的中间状态这能帮助你快速定位问题所在。5. 复杂度分析与优化5.1 时间复杂度两种解法的时间复杂度都是O(amount * n)其中n是硬币/数字的数量。5.2 空间优化两种解法都可以优化空间复杂度到O(amount)因为我们只需要一维的dp数组。上面的代码已经实现了这种优化。5.3 组合总和Ⅳ的进阶考虑在某些语言中当target很大时结果可能会超出整数范围。在实际面试中可以询问面试官是否需要考虑这种情况以及如何处理比如取模等。6. 实际应用与扩展6.1 零钱兑换的实际应用零钱兑换问题在金融领域有广泛应用比如自动售货机的找零系统银行的外汇兑换计算支付系统的组合支付方式计算6.2 组合总和的实际应用组合总和问题可以应用于密码破解中的尝试组合计算游戏中的技能组合效果计算广告投放中的组合策略效果评估6.3 问题变种掌握了这两个基础问题后可以尝试解决它们的变种硬币有限的情况多重背包问题要求返回具体的组合而不仅仅是计数加入额外的约束条件如最少硬币数等7. 个人解题心得在解决这类动态规划问题时我总结了以下几点经验先明确问题是否考虑顺序 - 这是选择解法方向的关键画图辅助理解 - 对于dp数组的变化过程简单的示例图能大大提升理解从小例子开始 - 先用小的amount和nums手动计算验证思路重视初始化 - dp[0]的初始化经常是解决问题的关键打印中间状态 - 这是调试动态规划问题的最有效方法对于面试准备建议将这两个问题与以下问题一起练习爬楼梯问题背包问题系列分割等和子集目标和这样能够建立起完整的动态规划知识体系应对各种变种问题。