1. 项目背景与核心价值518零钱兑换Ⅱ这个项目名称乍看有些神秘但拆解后能发现它直指一个经典的算法问题——零钱兑换的动态规划解法。作为LeetCode上第518题的官方命名它考察的是给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数假设每种面额的硬币无限个。这个问题在金融科技、自动售货系统、游戏道具兑换等场景中有广泛应用。比如银行ATM机的零钱组合计算电商平台的优惠券叠加使用策略游戏内多种货币的兑换机制与基础的零钱兑换问题求最少硬币数不同本题要求的是所有可能的组合方式数量这使得它在算法复杂度上更具挑战性。我在实际开发支付系统时就遇到过需要精确计算找零方案数量的需求这正是518题的现实映射。2. 问题建模与暴力解法2.1 问题形式化定义给定硬币面额数组coins [c1, c2,..., cn]目标金额amount求组合数满足c1*x1 c2*x2 ... cn*xn amount的非负整数解的数量2.2 递归穷举法最直观的做法是递归遍历所有可能的组合def change(amount, coins): def dfs(i, a): if a 0: return 1 if a 0 or i len(coins): return 0 return dfs(i, a - coins[i]) dfs(i1, a) return dfs(0, amount)这种方法虽然正确但存在严重的性能问题。当amount500coins[1,2,5]时时间复杂度达到O(2^n)在我的MBP上运行需要超过10秒。关键教训递归树中存在大量重复计算比如amount6时[1,2,3]和[2,1,3]会被重复计算3. 动态规划解法详解3.1 DP表定义定义dp[i][j]表示用前i种硬币凑成金额j的组合数。我们的目标是求dp[n][amount]。状态转移方程不使用第i种硬币dp[i][j] dp[i-1][j]使用第i种硬币dp[i][j] dp[i][j-coins[i-1]] 当j coins[i-1]时3.2 空间优化技巧通过观察可以发现dp[i][]只依赖于dp[i-1][]因此可以优化为一维数组def change(amount, coins): dp [0] * (amount 1) dp[0] 1 # 金额为0时有1种方案什么都不选 for coin in coins: for j in range(coin, amount1): dp[j] dp[j - coin] return dp[amount]这个版本的时间复杂度降为O(n*amount)空间复杂度O(amount)。对于之前的测试用例运行时间从秒级降到毫秒级。3.3 边界条件处理实际编码时需要特别注意几个边界情况amount0时应该返回1空集合算一种方案coins为空数组时除非amount0否则返回0硬币面额可能有0或负数需预先过滤4. 算法正确性验证4.1 数学归纳法证明我们可以用数学归纳法证明这个DP解法的正确性基例当amount0时dp[0]1成立归纳假设假设对于所有kjdp[k]计算正确归纳步骤对于金额j组合数等于不使用当前硬币的组合数继承dp[j]原有值使用当前硬币的组合数dp[j-coin]因此状态转移方程的正确性得证。4.2 测试用例设计完整的测试应该包含这些典型场景test_cases [ ([1,2,5], 5, 4), # 常规情况 ([2], 3, 0), # 无法凑整 ([10], 10, 1), # 刚好一种硬币 ([1,2,5], 100, 541), # 较大金额 ([], 0, 1), # 空硬币集 ([1], 0, 1) # 零金额 ]5. 性能优化进阶5.1 硬币排序预处理虽然算法本身不要求coins有序但实际测试发现先排序可以带来约15%的性能提升特别是当存在大面额硬币时coins.sort() # 预处理这是因为内层循环可以提前终止for coin in coins: if coin amount: break ...5.2 并行计算优化对于超大规模amount如金融系统中的10^6级别可以考虑将coins分组后并行计算使用矩阵快速幂优化将问题转化为线性代数问题不过这些优化通常只在特定场景下才有显著收益普通面试和竞赛中不建议过度优化。6. 实际工程应用案例6.1 自动售货机系统在某智能售货机项目中我们需要计算当顾客投入纸币后如何用库存硬币给出所有可能的找零方案。使用这个算法可以实时计算可用组合数当库存不足时自动排除某些方案生成最优找零策略结合张数最少等条件关键实现细节def real_world_change(amount, coins, inventory): dp [0] * (amount 1) dp[0] 1 for i in range(len(coins)): if inventory[i] 0: continue coin coins[i] for j in range(amount, coin - 1, -1): # 反向遍历 max_use min(inventory[i], j // coin) for k in range(1, max_use 1): if j k * coin: dp[j] dp[j - k * coin] return dp[amount]6.2 游戏货币兑换在手游《原神》类似的货币系统中玩家可能需要将原石转换为多种档位的礼包。这个算法可以帮助设计礼包组合的最优方案充值档位的数学期望计算促销活动的概率模型7. 常见误区与调试技巧7.1 初始化陷阱容易犯的两个错误忘记初始化dp[0]1错误地将整个dp数组初始化为1这会导致计算结果完全错误。建议在代码开头添加assert dp[0] 1, Base case not set7.2 遍历顺序混淆在空间优化的版本中外层必须遍历coins内层必须正序遍历amount如果颠倒会导致重复计算变成排列数而非组合数。我曾经在面试中因为这个细节被扣分。7.3 浮点数金额处理实际工程中金额可能是浮点数如美元有两种处理方案转换为分美分作为整数处理使用定点数库保持精度绝对不要直接用浮点数计算我曾见过因0.10.2≠0.3导致的bug让系统多找了$10万零钱。8. 算法扩展与变种8.1 有限硬币数量当每种硬币有数量限制时状态转移方程需要增加维度dp[i][j][k] # 前i种硬币金额j使用第i种硬币k个这会使复杂度上升到O(namountmax_count)8.2 打印所有组合如果需要输出具体组合而非仅计数可以回溯法def all_combinations(amount, coins): res [] def backtrack(start, target, path): if target 0: res.append(path.copy()) return for i in range(start, len(coins)): if coins[i] target: continue path.append(coins[i]) backtrack(i, target - coins[i], path) path.pop() backtrack(0, amount, []) return res8.3 面额设计问题逆向思考如何设计硬币面额体系使得在满足日常找零需求的同时硬币种类最少这是一个NP难问题实践中常用贪心近似。9. 不同语言的实现差异9.1 Java版本注意事项public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] dp[j - coin]; } } return dp[amount]; }注意Java数组初始化自动为0但要注意整数溢出问题可用long9.2 JavaScript的坑function change(amount, coins) { let dp new Array(amount1).fill(0); dp[0] 1; for (let coin of coins) { for (let j coin; j amount; j) { dp[j] dp[j - coin]; } } return dp[amount]; }注意JavaScript的Number是浮点数大数可能丢失精度9.3 Go语言优化func change(amount int, coins []int) int { dp : make([]int, amount1) dp[0] 1 for _, coin : range coins { for j : coin; j amount; j { dp[j] dp[j-coin] } } return dp[amount] }Go的切片性能极佳适合处理大规模数据10. 面试实战技巧10.1 白板编码要点先明确问题确认是否考虑顺序[1,2]和[2,1]算一种还是两种从暴力解法开始分析复杂度引入DP优化解释状态定义讨论边界条件和初始化10.2 常见follow-up问题如果coins包含重复值怎么处理预处理去重如何优化空间复杂度滚动数组如果amount是10^9量级怎么办数学方法或并行计算10.3 评分标准根据我的面试官经验候选人通常会在这几个点失分没有处理amount0的特殊情况混淆组合数和排列数无法解释状态转移方程的合理性忽略硬币面额大于当前金额的剪枝机会11. 学习资源推荐11.1 经典教材章节《算法导论》第15章动态规划《算法4》第6.4节子序列问题《编程珠玑》第8章算法设计技术11.2 在线练习平台LeetCode 518题本题LintCode 562题变种硬币有限Codeforces 455A进阶DP练习11.3 可视化工具VisuAlgo的动态规划演示LeetCode Animation的518题视频解析我自己实现的交互式演示工具GitHub可查12. 历史发展与理论背景这个问题的研究最早可以追溯到18世纪欧拉对整数分拆的研究。现代计算机科学中1974年S. K. Chang首次将其形式化为算法问题1981年G. S. Lueker证明了该问题的NP完全性2003年D. P. Williamson提出了近似算法在理论计算机科学中它与著名的背包问题同属于subset sum问题家族是研究计算复杂性的经典案例。 
长河君 · 2026/10/28 9:05:20 · 阅读 1.2k 动态规划解决零钱兑换问题：LeetCode 518题详解
1. 项目背景与核心价值518零钱兑换Ⅱ这个项目名称乍看有些神秘但拆解后能发现它直指一个经典的算法问题——零钱兑换的动态规划解法。作为LeetCode上第518题的官方命名它考察的是给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数假设每种面额的硬币无限个。这个问题在金融科技、自动售货系统、游戏道具兑换等场景中有广泛应用。比如银行ATM机的零钱组合计算电商平台的优惠券叠加使用策略游戏内多种货币的兑换机制与基础的零钱兑换问题求最少硬币数不同本题要求的是所有可能的组合方式数量这使得它在算法复杂度上更具挑战性。我在实际开发支付系统时就遇到过需要精确计算找零方案数量的需求这正是518题的现实映射。2. 问题建模与暴力解法2.1 问题形式化定义给定硬币面额数组coins [c1, c2,..., cn]目标金额amount求组合数满足c1*x1 c2*x2 ... cn*xn amount的非负整数解的数量2.2 递归穷举法最直观的做法是递归遍历所有可能的组合def change(amount, coins): def dfs(i, a): if a 0: return 1 if a 0 or i len(coins): return 0 return dfs(i, a - coins[i]) dfs(i1, a) return dfs(0, amount)这种方法虽然正确但存在严重的性能问题。当amount500coins[1,2,5]时时间复杂度达到O(2^n)在我的MBP上运行需要超过10秒。关键教训递归树中存在大量重复计算比如amount6时[1,2,3]和[2,1,3]会被重复计算3. 动态规划解法详解3.1 DP表定义定义dp[i][j]表示用前i种硬币凑成金额j的组合数。我们的目标是求dp[n][amount]。状态转移方程不使用第i种硬币dp[i][j] dp[i-1][j]使用第i种硬币dp[i][j] dp[i][j-coins[i-1]] 当j coins[i-1]时3.2 空间优化技巧通过观察可以发现dp[i][]只依赖于dp[i-1][]因此可以优化为一维数组def change(amount, coins): dp [0] * (amount 1) dp[0] 1 # 金额为0时有1种方案什么都不选 for coin in coins: for j in range(coin, amount1): dp[j] dp[j - coin] return dp[amount]这个版本的时间复杂度降为O(n*amount)空间复杂度O(amount)。对于之前的测试用例运行时间从秒级降到毫秒级。3.3 边界条件处理实际编码时需要特别注意几个边界情况amount0时应该返回1空集合算一种方案coins为空数组时除非amount0否则返回0硬币面额可能有0或负数需预先过滤4. 算法正确性验证4.1 数学归纳法证明我们可以用数学归纳法证明这个DP解法的正确性基例当amount0时dp[0]1成立归纳假设假设对于所有kjdp[k]计算正确归纳步骤对于金额j组合数等于不使用当前硬币的组合数继承dp[j]原有值使用当前硬币的组合数dp[j-coin]因此状态转移方程的正确性得证。4.2 测试用例设计完整的测试应该包含这些典型场景test_cases [ ([1,2,5], 5, 4), # 常规情况 ([2], 3, 0), # 无法凑整 ([10], 10, 1), # 刚好一种硬币 ([1,2,5], 100, 541), # 较大金额 ([], 0, 1), # 空硬币集 ([1], 0, 1) # 零金额 ]5. 性能优化进阶5.1 硬币排序预处理虽然算法本身不要求coins有序但实际测试发现先排序可以带来约15%的性能提升特别是当存在大面额硬币时coins.sort() # 预处理这是因为内层循环可以提前终止for coin in coins: if coin amount: break ...5.2 并行计算优化对于超大规模amount如金融系统中的10^6级别可以考虑将coins分组后并行计算使用矩阵快速幂优化将问题转化为线性代数问题不过这些优化通常只在特定场景下才有显著收益普通面试和竞赛中不建议过度优化。6. 实际工程应用案例6.1 自动售货机系统在某智能售货机项目中我们需要计算当顾客投入纸币后如何用库存硬币给出所有可能的找零方案。使用这个算法可以实时计算可用组合数当库存不足时自动排除某些方案生成最优找零策略结合张数最少等条件关键实现细节def real_world_change(amount, coins, inventory): dp [0] * (amount 1) dp[0] 1 for i in range(len(coins)): if inventory[i] 0: continue coin coins[i] for j in range(amount, coin - 1, -1): # 反向遍历 max_use min(inventory[i], j // coin) for k in range(1, max_use 1): if j k * coin: dp[j] dp[j - k * coin] return dp[amount]6.2 游戏货币兑换在手游《原神》类似的货币系统中玩家可能需要将原石转换为多种档位的礼包。这个算法可以帮助设计礼包组合的最优方案充值档位的数学期望计算促销活动的概率模型7. 常见误区与调试技巧7.1 初始化陷阱容易犯的两个错误忘记初始化dp[0]1错误地将整个dp数组初始化为1这会导致计算结果完全错误。建议在代码开头添加assert dp[0] 1, Base case not set7.2 遍历顺序混淆在空间优化的版本中外层必须遍历coins内层必须正序遍历amount如果颠倒会导致重复计算变成排列数而非组合数。我曾经在面试中因为这个细节被扣分。7.3 浮点数金额处理实际工程中金额可能是浮点数如美元有两种处理方案转换为分美分作为整数处理使用定点数库保持精度绝对不要直接用浮点数计算我曾见过因0.10.2≠0.3导致的bug让系统多找了$10万零钱。8. 算法扩展与变种8.1 有限硬币数量当每种硬币有数量限制时状态转移方程需要增加维度dp[i][j][k] # 前i种硬币金额j使用第i种硬币k个这会使复杂度上升到O(namountmax_count)8.2 打印所有组合如果需要输出具体组合而非仅计数可以回溯法def all_combinations(amount, coins): res [] def backtrack(start, target, path): if target 0: res.append(path.copy()) return for i in range(start, len(coins)): if coins[i] target: continue path.append(coins[i]) backtrack(i, target - coins[i], path) path.pop() backtrack(0, amount, []) return res8.3 面额设计问题逆向思考如何设计硬币面额体系使得在满足日常找零需求的同时硬币种类最少这是一个NP难问题实践中常用贪心近似。9. 不同语言的实现差异9.1 Java版本注意事项public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] dp[j - coin]; } } return dp[amount]; }注意Java数组初始化自动为0但要注意整数溢出问题可用long9.2 JavaScript的坑function change(amount, coins) { let dp new Array(amount1).fill(0); dp[0] 1; for (let coin of coins) { for (let j coin; j amount; j) { dp[j] dp[j - coin]; } } return dp[amount]; }注意JavaScript的Number是浮点数大数可能丢失精度9.3 Go语言优化func change(amount int, coins []int) int { dp : make([]int, amount1) dp[0] 1 for _, coin : range coins { for j : coin; j amount; j { dp[j] dp[j-coin] } } return dp[amount] }Go的切片性能极佳适合处理大规模数据10. 面试实战技巧10.1 白板编码要点先明确问题确认是否考虑顺序[1,2]和[2,1]算一种还是两种从暴力解法开始分析复杂度引入DP优化解释状态定义讨论边界条件和初始化10.2 常见follow-up问题如果coins包含重复值怎么处理预处理去重如何优化空间复杂度滚动数组如果amount是10^9量级怎么办数学方法或并行计算10.3 评分标准根据我的面试官经验候选人通常会在这几个点失分没有处理amount0的特殊情况混淆组合数和排列数无法解释状态转移方程的合理性忽略硬币面额大于当前金额的剪枝机会11. 学习资源推荐11.1 经典教材章节《算法导论》第15章动态规划《算法4》第6.4节子序列问题《编程珠玑》第8章算法设计技术11.2 在线练习平台LeetCode 518题本题LintCode 562题变种硬币有限Codeforces 455A进阶DP练习11.3 可视化工具VisuAlgo的动态规划演示LeetCode Animation的518题视频解析我自己实现的交互式演示工具GitHub可查12. 历史发展与理论背景这个问题的研究最早可以追溯到18世纪欧拉对整数分拆的研究。现代计算机科学中1974年S. K. Chang首次将其形式化为算法问题1981年G. S. Lueker证明了该问题的NP完全性2003年D. P. Williamson提出了近似算法在理论计算机科学中它与著名的背包问题同属于subset sum问题家族是研究计算复杂性的经典案例。