零钱兑换 IICoin Change II从递归决策树到一维 DP 的完整计数解法详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 hints/coin-change-ii.md 的解题提示为主线结合 articles/coin-change-ii.md 的完整题解与仓库内 12 种语言的实现源码系统讲解 LeetCode 518「零钱兑换 II」——如何在硬币无限可用、且组合顺序无关的前提下统计组成给定金额的方案总数。读完本文你将掌握递归决策树的建模方法、如何通过「停留在同一索引」实现同一硬币的多次选取、Memoization 与 2D/1D 动态规划的递推与优化全过程以及组合计数与排列计数在循环顺序上的本质区别。问题定义与核心难点给定一个整数数组coins表示不同面额的硬币和一个整数amount总金额返回组成该金额的组合数。每枚硬币可以无限次使用且组合中硬币的排列顺序不区分先后即[1, 2]与[2, 1]视为同一种组合。例如amount 5coins [1, 2, 5]答案为4对应组合为52 2 12 1 1 11 1 1 1 1这一描述可在仓库 cpp/0518-coin-change-ii.cpp 的注释中直接找到仓库内该题的多语言解法均围绕这一语义实现README.md 完成度表中列出了该题在 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、Swift、TypeScript 等语言的提交情况。核心难点有二硬币可无限复用——递归时不能简单跳到下一个索引而要允许「停在当前索引继续取同一枚硬币」组合而非排列——同样的硬币集合不能因顺序不同被重复计数这直接决定了 DP 循环的嵌套顺序。前置知识在开始前建议先熟悉以下四块基础对应 articles/coin-change-ii.md 的 Prerequisites 部分知识模块作用递归Recursion将问题分解为「选 / 不选」两个子问题是决策树建模的基础动态规划·记忆化Memoization缓存(i, a)状态的结果消除递归中的重复计算动态规划·表格化Tabulation自底向上填充 DP 表避免递归栈开销完全背包模式Unbounded Knapsack物品可无限取用时的计数 DP正是本题的抽象原型hint 文档hints/coin-change-ii.md同时给出了本体的目标复杂度时间O(n * a)、空间O(n * a)n为硬币种数a为金额。下面从最朴素的递归开始逐步逼近这一目标。方法一递归决策树直觉每一步针对当前硬币做出两个选择跳过skip不取当前硬币索引i 1继续选取use取一枚当前硬币剩余金额减去coins[i]索引保持不变以允许再次取用。于是递归函数可以定义为dfs(i, a)用索引i及其之后的硬币组成剩余金额a的方案数。对硬币排序并始终沿列表向前移动可以保证同一组合不会以不同顺序被重复统计。算法步骤将硬币面额排序保证顺序一致定义递归函数dfs(i, a)i当前硬币索引a剩余金额若a 0返回1形成一个有效组合若i越界硬币耗尽返回0无法组成初始化结果计数器res 0若当前硬币可用a coins[i]分支一跳过当前硬币 →dfs(i 1, a)分支二使用当前硬币 →dfs(i, a - coins[i])索引不变两者相加累入res返回res从dfs(0, amount)开始。代码实现节选class Solution: def change(self, amount: int, coins: List[int]) - int: coins.sort() def dfs(i, a): if a 0: return 1 if i len(coins): return 0 res 0 if a coins[i]: res dfs(i 1, a) res dfs(i, a - coins[i]) return res return dfs(0, amount)class Solution { public: int change(int amount, vectorint coins) { sort(coins.begin(), coins.end()); return dfs(coins, 0, amount); } private: int dfs(const vectorint coins, int i, int a) { if (a 0) return 1; if (i coins.size()) return 0; int res 0; if (a coins[i]) { res dfs(coins, i 1, a); res dfs(coins, i, a - coins[i]); } return res; } };仓库中 javascript/0518-coin-change-ii.js 提供了另一种等价视角的暴力 DFS以n表示剩余可用的硬币种数amount coins[n-1]时直接跳到下一种硬币否则把「用当前硬币」与「不用当前硬币」两个分支相加。复杂度分析时间复杂度O(2 ^ max(n, a/m))空间复杂度O(max(n, a/m))其中n为硬币种数a为金额m为所有硬币中的最小面额。当金额或硬币种数稍大时指数级开销不可接受。hint 3hints/coin-change-ii.md明确指出这一方案是指数级的必须想办法避免冗余计算。方法二动态规划·自顶向下记忆化直觉纯递归会反复求解同一批子问题。例如金额5、硬币[1, 2, 5]时状态(i, a)会被大量重复访问。为此引入记忆化每个状态由两个量唯一确定当前硬币索引i剩余金额a。用哈希表或二维数组缓存memo[i][a]命中即返回避免重复计算对应 hint 4 的建议hints/coin-change-ii.md。算法步骤排序硬币建立二维记忆表memomemo[i][a]表示用索引i及其之后的硬币组成金额a的方案数定义dfs(i, a)与递归版本相同的语义a 0→ 返回1i越界 → 返回0memo[i][a]已计算 → 直接返回缓存值初始化res 0若a coins[i]res dfs(i 1, a) dfs(i, a - coins[i])写入memo[i][a]并返回从dfs(0, amount)开始最终返回结果。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: coins.sort() memo [[-1] * (amount 1) for _ in range(len(coins) 1)] def dfs(i, a): if a 0: return 1 if i len(coins): return 0 if memo[i][a] ! -1: return memo[i][a] res 0 if a coins[i]: res dfs(i 1, a) res dfs(i, a - coins[i]) memo[i][a] res return res return dfs(0, amount)public class Solution { public int change(int amount, int[] coins) { Arrays.sort(coins); int[][] memo new int[coins.length 1][amount 1]; for (int[] row : memo) Arrays.fill(row, -1); return dfs(0, amount, coins, memo); } private int dfs(int i, int a, int[] coins, int[][] memo) { if (a 0) return 1; if (i coins.length) return 0; if (memo[i][a] ! -1) return memo[i][a]; int res 0; if (a coins[i]) { res dfs(i 1, a, coins, memo); res dfs(i, a - coins[i], coins, memo); } memo[i][a] res; return res; } }class Solution { public: int change(int amount, vectorint coins) { sort(coins.begin(), coins.end()); vectorvectorint memo(coins.size() 1, vectorint(amount 1, -1)); return dfs(0, amount, coins, memo); } int dfs(int i, int a, vectorint coins, vectorvectorint memo) { if (a 0) return 1; if (i coins.size()) return 0; if (memo[i][a] ! -1) return memo[i][a]; int res 0; if (a coins[i]) { res dfs(i 1, a, coins, memo); res dfs(i, a - coins[i], coins, memo); } memo[i][a] res; return res; } };其余语言JavaScript、C#、Go、Kotlin、Swift、Rust的同构实现可在 articles/coin-change-ii.md 中查看。仓库中 python/0518-coin-change-ii.py 的记忆化实现采用「累加视角」从(i, 0)出发dfs(i, a coins[i])表示取一枚当前硬币dfs(i 1, a)表示跳到下一种硬币命中amount即返回1。两种视角剩余金额递减 / 已累计金额递增数学上等价后者配合字典缓存(i, a)键同样保证O(n * a)时间与O(n * a)空间。C 版cpp/0518-coin-change-ii.cpp则用mappairint,int, int作为记忆结构语义注释为「(index, sum) - # of combos that make up this amount」。复杂度分析时间复杂度O(n * a)空间复杂度O(n * a)方法三动态规划·自底向上2D 表格直觉递归 记忆化本质上是「自顶向下」填表完全可以把同样的递推关系改成自底向上先用边界条件把表填满答案自然落在dp[0][amount]。状态定义沿用dp[i][a]表示用索引i及其之后的硬币组成金额a的方案数。算法步骤排序硬币设n为硬币种数建立(n 1) x (amount 1)的 DP 表dp初始化边界任意i都有dp[i][0] 1金额为 0 只有一种方式——不选任何硬币逆序遍历硬币索引in-1到0对每个i遍历金额a0到amount若a coins[i]跳过当前硬币dp[i 1][a]使用当前硬币dp[i][a - coins[i]]两者相加得dp[i][a]答案为dp[0][amount]。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: n len(coins) coins.sort() dp [[0] * (amount 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] 1 for i in range(n - 1, -1, -1): for a in range(amount 1): if a coins[i]: dp[i][a] dp[i 1][a] dp[i][a] dp[i][a - coins[i]] return dp[0][amount]public class Solution { public int change(int amount, int[] coins) { int n coins.length; Arrays.sort(coins); int[][] dp new int[n 1][amount 1]; for (int i 0; i n; i) dp[i][0] 1; for (int i n - 1; i 0; i--) { for (int a 0; a amount; a) { if (a coins[i]) { dp[i][a] dp[i 1][a]; dp[i][a] dp[i][a - coins[i]]; } } } return dp[0][amount]; } }class Solution { public: int change(int amount, vectorint coins) { int n coins.size(); sort(coins.begin(), coins.end()); vectorvectoruint dp(n 1, vectoruint(amount 1, 0)); for (int i 0; i n; i) dp[i][0] 1; for (int i n - 1; i 0; i--) { for (int a 0; a amount; a) { if (a coins[i]) { dp[i][a] dp[i 1][a]; dp[i][a] dp[i][a - coins[i]]; } } } return dp[0][amount]; } };JavaScript、C#、Go、Kotlin、Swift、Rust 的 2D 表格实现细节含 Go 中a coins[i]时显式继承dp[i1][a]、Swift 中为防溢出的Int.max检查等见 articles/coin-change-ii.md。仓库内 kotlin/0518-coin-change-ii.kt 的第二版实现是等价的二维表格写法每行首列置 1dp[i][j]继承上一行不用当前硬币并加上同行更小金额再用一枚当前硬币。复杂度分析时间复杂度O(n * a)空间复杂度O(n * a)方法四动态规划·空间优化滚动一维数组直觉观察 2D 递推式dp[i][a]只依赖两处下一行跳过硬币dp[i 1][a]当前行使用硬币dp[i][a - coins[i]]。因此每一行只与相邻行相关可以用两个一维数组滚动替代整张二维表空间降至O(a)。仓库中的 go/0518-coin-change-ii.go 正是这一思路的 Go 实现外层逆序遍历硬币nextRow[a] row[a]完成「跳过」的继承再叠加nextRow[a - coins[i]]完成「使用」的累加每轮处理完将row指向nextRow。算法步骤建立一维数组dp长度amount 1dp[a]表示用已处理的硬币组成金额a的方案数初始化dp[0] 1逆序遍历硬币新建nextDP并置nextDP[0] 1遍历金额a1到amount先继承dp[a]跳过当前硬币若a - coins[i] 0累加nextDP[a - coins[i]]再用一枚当前硬币处理完当前硬币后dp nextDP全部处理完dp[amount]即答案。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: dp [0] * (amount 1) dp[0] 1 for i in range(len(coins) - 1, -1, -1): nextDP [0] * (amount 1) nextDP[0] 1 for a in range(1, amount 1): nextDP[a] dp[a] if a - coins[i] 0: nextDP[a] nextDP[a - coins[i]] dp nextDP return dp[amount]public class Solution { public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int i coins.length - 1; i 0; i--) { int[] nextDP new int[amount 1]; nextDP[0] 1; for (int a 1; a amount; a) { nextDP[a] dp[a]; if (a - coins[i] 0) { nextDP[a] nextDP[a - coins[i]]; } } dp nextDP; } return dp[amount]; } }class Solution { public: int change(int amount, vectorint coins) { vectoruint dp(amount 1, 0); dp[0] 1; for (int i coins.size() - 1; i 0; i--) { vectoruint nextDP(amount 1, 0); nextDP[0] 1; for (int a 1; a amount; a) { nextDP[a] dp[a]; if (a - coins[i] 0) { nextDP[a] nextDP[a - coins[i]]; } } dp nextDP; } return dp[amount]; } };Go、JavaScript、Kotlin、Swift、Rust 的实现见 articles/coin-change-ii.md其中 python/0518-coin-change-ii.py 的第三个版本即本方法的 Python 落地。Swift 与 Kotlin 版本额外加入了整数溢出防护Int.max检查、System.arraycopy回填。复杂度分析时间复杂度O(n * a)空间复杂度O(a)方法五动态规划·最优原地更新一维数组直觉既然「跳过」只是把旧值原样继承「使用」只是叠加同数组更小金额的值那么在正确的遍历顺序下可以直接在同一个一维数组上原地累加连滚动数组都省去dp[a]始终表示「用已处理过的硬币组成金额a的方案数」每个硬币只依赖「同金额的旧值」与「更小金额的新值」。关键在于外循环是硬币、内循环是金额——这一顺序同时保证了同一硬币可无限复用内层正向扫描时dp[a - coin]已包含当前硬币且不同组合不会因顺序重复计数。算法步骤建立一维数组dp长度amount 1dp[a]表示组成金额a的方案数初始化dp[0] 1逆序遍历硬币对每个硬币正向遍历金额a1到amount若coin adp[a] dp[a - coin]全部处理完返回dp[amount]。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: dp [0] * (amount 1) dp[0] 1 for i in range(len(coins) - 1, -1, -1): for a in range(1, amount 1): dp[a] dp[a - coins[i]] if coins[i] a else 0 return dp[amount]public class Solution { public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int i coins.length - 1; i 0; i--) for (int a 1; a amount; a) dp[a] dp[a] (coins[i] a ? dp[a - coins[i]] : 0); return dp[amount]; } }class Solution { public: int change(int amount, vectorint coins) { vectoruint dp(amount 1, 0); dp[0] 1; for (int i coins.size() - 1; i 0; i--) { for (int a 1; a amount; a) { dp[a] dp[a] (coins[i] a ? dp[a - coins[i]] : 0); } } return dp[amount]; } };class Solution { /** * param {number} amount * param {number[]} coins * return {number} */ change(amount, coins) { const dp new Array(amount 1).fill(0); dp[0] 1; for (let i coins.length - 1; i 0; i--) { for (let a 1; a amount; a) { dp[a] coins[i] a ? dp[a - coins[i]] : 0; } } return dp[amount]; } }int change(int amount, int* coins, int coinsSize){ if (coinsSize 0) { return amount 0; } int* dp calloc((amount 1), sizeof(int)); dp[0] 1; for (int i 0; i coinsSize; i) { for (int j coins[i]; j amount; j) { dp[j] dp[j - coins[i]]; } } int ans dp[amount]; free(dp); return ans; }C、Rust、Kotlin 版本的实现都采用了「外层硬币、内层金额、正向扫描」的简洁形态c/0518-coin-change-ii.c 直接从j coins[i]起步规避负索引rust/0518-coin-change-ii.rs 用for i in c..n做相同的事并返回dp末元素kotlin/0518-coin-change-ii.kt 的第一版即最优一维解java/0518-coin-change-ii.java 的注释清晰标注了该解法的复杂度为O(n * amount)时间、O(amount)空间。复杂度分析时间复杂度O(n * a)空间复杂度O(a)五种方案对比速查方案核心思想时间复杂度空间复杂度1. 递归决策树跳过 / 使用指数搜索O(2^max(n, a/m))O(max(n, a/m))2. 自顶向下 DP递归 memo[i][a]记忆化O(n * a)O(n * a)3. 自底向上 DP2D 表格逆序填表O(n * a)O(n * a)4. 空间优化 DP滚动一维数组nextDPO(n * a)O(a)5. 最优 DP原地更新一维数组O(n * a)O(a)其中n为硬币种数a为金额m为最小硬币面额。方法 5 同时达到了 hint 文档要求的O(n * a)时间目标且空间进一步压至O(a)是面试与工程实践中的首选写法。常见陷阱陷阱一把组合数数成了排列数外层循环是金额、内层循环是硬币时[1, 2]与[2, 1]会被当成两种不同方案结果是排列数而非组合数# 错误数出的是排列数 for a in range(1, amount 1): for coin in coins: dp[a] dp[a - coin] # 正确硬币在外层数出的是组合数 for coin in coins: for a in range(coin, amount 1): dp[a] dp[a - coin]这正是本题与 0377 - Combination Sum IV排列计数金额在外层的本质区别。相关的组合计数题还包括 0039 - Combination Sum 与 0040 - Combination Sum II可与本题放在一起对照学习。陷阱二忘记初始化dp[0] 1dp[0]代表「金额 0 恰好有一种合法方式——一枚硬币都不选」。不初始化它所有金额的方案数都会是 0。这一边界在仓库的每一份实现如 go/0518-coin-change-ii.go 的row[0] 1中都得到了严格保留。陷阱三允许负数下标访问访问dp[a - coins[i]]前必须确认a coins[i]否则会造成负索引或越界错误# 错误可能访问负索引 dp[a] dp[a - coins[i]] # 正确先检查再访问 if a coins[i]: dp[a] dp[a - coins[i]]C 语言版从j coins[i]开始内层循环c/0518-coin-change-ii.cRust 版用for i in c..nrust/0518-coin-change-ii.rs都是从循环边界上根除这一隐患的做法。总结零钱兑换 II 是「完全背包 组合计数」的教科书级题目其解题链条非常清晰递归建立决策树心智模型每个状态只有「跳过」与「使用停在原地」两个分支记忆化消除指数级的重复子问题达到O(n * a)自底向上用 2D 表格复现同一递推去掉递归栈开销滚动数组 / 原地更新利用「行间依赖」将空间压到O(a)最终记住硬币在外层、金额在内层、正向扫描——这是组合计数的黄金三要素。本仓库为该题提供了 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、Swift、TypeScript 等多语言实现完整解法逐语言展开见 articles/coin-change-ii.md解题思路的渐进式提示见 hints/coin-change-ii.md各语言提交状态可对照 README.md 完成度表。掌握本题后可继续挑战 0322 - Coin Change求最少硬币数等变体进一步理解「计数」与「最优化」两类完全背包问题的异同。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 零钱兑换 II（Coin Change II）：从递归决策树到一维 DP 的完整计数解法详解
零钱兑换 IICoin Change II从递归决策树到一维 DP 的完整计数解法详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 hints/coin-change-ii.md 的解题提示为主线结合 articles/coin-change-ii.md 的完整题解与仓库内 12 种语言的实现源码系统讲解 LeetCode 518「零钱兑换 II」——如何在硬币无限可用、且组合顺序无关的前提下统计组成给定金额的方案总数。读完本文你将掌握递归决策树的建模方法、如何通过「停留在同一索引」实现同一硬币的多次选取、Memoization 与 2D/1D 动态规划的递推与优化全过程以及组合计数与排列计数在循环顺序上的本质区别。问题定义与核心难点给定一个整数数组coins表示不同面额的硬币和一个整数amount总金额返回组成该金额的组合数。每枚硬币可以无限次使用且组合中硬币的排列顺序不区分先后即[1, 2]与[2, 1]视为同一种组合。例如amount 5coins [1, 2, 5]答案为4对应组合为52 2 12 1 1 11 1 1 1 1这一描述可在仓库 cpp/0518-coin-change-ii.cpp 的注释中直接找到仓库内该题的多语言解法均围绕这一语义实现README.md 完成度表中列出了该题在 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、Swift、TypeScript 等语言的提交情况。核心难点有二硬币可无限复用——递归时不能简单跳到下一个索引而要允许「停在当前索引继续取同一枚硬币」组合而非排列——同样的硬币集合不能因顺序不同被重复计数这直接决定了 DP 循环的嵌套顺序。前置知识在开始前建议先熟悉以下四块基础对应 articles/coin-change-ii.md 的 Prerequisites 部分知识模块作用递归Recursion将问题分解为「选 / 不选」两个子问题是决策树建模的基础动态规划·记忆化Memoization缓存(i, a)状态的结果消除递归中的重复计算动态规划·表格化Tabulation自底向上填充 DP 表避免递归栈开销完全背包模式Unbounded Knapsack物品可无限取用时的计数 DP正是本题的抽象原型hint 文档hints/coin-change-ii.md同时给出了本体的目标复杂度时间O(n * a)、空间O(n * a)n为硬币种数a为金额。下面从最朴素的递归开始逐步逼近这一目标。方法一递归决策树直觉每一步针对当前硬币做出两个选择跳过skip不取当前硬币索引i 1继续选取use取一枚当前硬币剩余金额减去coins[i]索引保持不变以允许再次取用。于是递归函数可以定义为dfs(i, a)用索引i及其之后的硬币组成剩余金额a的方案数。对硬币排序并始终沿列表向前移动可以保证同一组合不会以不同顺序被重复统计。算法步骤将硬币面额排序保证顺序一致定义递归函数dfs(i, a)i当前硬币索引a剩余金额若a 0返回1形成一个有效组合若i越界硬币耗尽返回0无法组成初始化结果计数器res 0若当前硬币可用a coins[i]分支一跳过当前硬币 →dfs(i 1, a)分支二使用当前硬币 →dfs(i, a - coins[i])索引不变两者相加累入res返回res从dfs(0, amount)开始。代码实现节选class Solution: def change(self, amount: int, coins: List[int]) - int: coins.sort() def dfs(i, a): if a 0: return 1 if i len(coins): return 0 res 0 if a coins[i]: res dfs(i 1, a) res dfs(i, a - coins[i]) return res return dfs(0, amount)class Solution { public: int change(int amount, vectorint coins) { sort(coins.begin(), coins.end()); return dfs(coins, 0, amount); } private: int dfs(const vectorint coins, int i, int a) { if (a 0) return 1; if (i coins.size()) return 0; int res 0; if (a coins[i]) { res dfs(coins, i 1, a); res dfs(coins, i, a - coins[i]); } return res; } };仓库中 javascript/0518-coin-change-ii.js 提供了另一种等价视角的暴力 DFS以n表示剩余可用的硬币种数amount coins[n-1]时直接跳到下一种硬币否则把「用当前硬币」与「不用当前硬币」两个分支相加。复杂度分析时间复杂度O(2 ^ max(n, a/m))空间复杂度O(max(n, a/m))其中n为硬币种数a为金额m为所有硬币中的最小面额。当金额或硬币种数稍大时指数级开销不可接受。hint 3hints/coin-change-ii.md明确指出这一方案是指数级的必须想办法避免冗余计算。方法二动态规划·自顶向下记忆化直觉纯递归会反复求解同一批子问题。例如金额5、硬币[1, 2, 5]时状态(i, a)会被大量重复访问。为此引入记忆化每个状态由两个量唯一确定当前硬币索引i剩余金额a。用哈希表或二维数组缓存memo[i][a]命中即返回避免重复计算对应 hint 4 的建议hints/coin-change-ii.md。算法步骤排序硬币建立二维记忆表memomemo[i][a]表示用索引i及其之后的硬币组成金额a的方案数定义dfs(i, a)与递归版本相同的语义a 0→ 返回1i越界 → 返回0memo[i][a]已计算 → 直接返回缓存值初始化res 0若a coins[i]res dfs(i 1, a) dfs(i, a - coins[i])写入memo[i][a]并返回从dfs(0, amount)开始最终返回结果。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: coins.sort() memo [[-1] * (amount 1) for _ in range(len(coins) 1)] def dfs(i, a): if a 0: return 1 if i len(coins): return 0 if memo[i][a] ! -1: return memo[i][a] res 0 if a coins[i]: res dfs(i 1, a) res dfs(i, a - coins[i]) memo[i][a] res return res return dfs(0, amount)public class Solution { public int change(int amount, int[] coins) { Arrays.sort(coins); int[][] memo new int[coins.length 1][amount 1]; for (int[] row : memo) Arrays.fill(row, -1); return dfs(0, amount, coins, memo); } private int dfs(int i, int a, int[] coins, int[][] memo) { if (a 0) return 1; if (i coins.length) return 0; if (memo[i][a] ! -1) return memo[i][a]; int res 0; if (a coins[i]) { res dfs(i 1, a, coins, memo); res dfs(i, a - coins[i], coins, memo); } memo[i][a] res; return res; } }class Solution { public: int change(int amount, vectorint coins) { sort(coins.begin(), coins.end()); vectorvectorint memo(coins.size() 1, vectorint(amount 1, -1)); return dfs(0, amount, coins, memo); } int dfs(int i, int a, vectorint coins, vectorvectorint memo) { if (a 0) return 1; if (i coins.size()) return 0; if (memo[i][a] ! -1) return memo[i][a]; int res 0; if (a coins[i]) { res dfs(i 1, a, coins, memo); res dfs(i, a - coins[i], coins, memo); } memo[i][a] res; return res; } };其余语言JavaScript、C#、Go、Kotlin、Swift、Rust的同构实现可在 articles/coin-change-ii.md 中查看。仓库中 python/0518-coin-change-ii.py 的记忆化实现采用「累加视角」从(i, 0)出发dfs(i, a coins[i])表示取一枚当前硬币dfs(i 1, a)表示跳到下一种硬币命中amount即返回1。两种视角剩余金额递减 / 已累计金额递增数学上等价后者配合字典缓存(i, a)键同样保证O(n * a)时间与O(n * a)空间。C 版cpp/0518-coin-change-ii.cpp则用mappairint,int, int作为记忆结构语义注释为「(index, sum) - # of combos that make up this amount」。复杂度分析时间复杂度O(n * a)空间复杂度O(n * a)方法三动态规划·自底向上2D 表格直觉递归 记忆化本质上是「自顶向下」填表完全可以把同样的递推关系改成自底向上先用边界条件把表填满答案自然落在dp[0][amount]。状态定义沿用dp[i][a]表示用索引i及其之后的硬币组成金额a的方案数。算法步骤排序硬币设n为硬币种数建立(n 1) x (amount 1)的 DP 表dp初始化边界任意i都有dp[i][0] 1金额为 0 只有一种方式——不选任何硬币逆序遍历硬币索引in-1到0对每个i遍历金额a0到amount若a coins[i]跳过当前硬币dp[i 1][a]使用当前硬币dp[i][a - coins[i]]两者相加得dp[i][a]答案为dp[0][amount]。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: n len(coins) coins.sort() dp [[0] * (amount 1) for _ in range(n 1)] for i in range(n 1): dp[i][0] 1 for i in range(n - 1, -1, -1): for a in range(amount 1): if a coins[i]: dp[i][a] dp[i 1][a] dp[i][a] dp[i][a - coins[i]] return dp[0][amount]public class Solution { public int change(int amount, int[] coins) { int n coins.length; Arrays.sort(coins); int[][] dp new int[n 1][amount 1]; for (int i 0; i n; i) dp[i][0] 1; for (int i n - 1; i 0; i--) { for (int a 0; a amount; a) { if (a coins[i]) { dp[i][a] dp[i 1][a]; dp[i][a] dp[i][a - coins[i]]; } } } return dp[0][amount]; } }class Solution { public: int change(int amount, vectorint coins) { int n coins.size(); sort(coins.begin(), coins.end()); vectorvectoruint dp(n 1, vectoruint(amount 1, 0)); for (int i 0; i n; i) dp[i][0] 1; for (int i n - 1; i 0; i--) { for (int a 0; a amount; a) { if (a coins[i]) { dp[i][a] dp[i 1][a]; dp[i][a] dp[i][a - coins[i]]; } } } return dp[0][amount]; } };JavaScript、C#、Go、Kotlin、Swift、Rust 的 2D 表格实现细节含 Go 中a coins[i]时显式继承dp[i1][a]、Swift 中为防溢出的Int.max检查等见 articles/coin-change-ii.md。仓库内 kotlin/0518-coin-change-ii.kt 的第二版实现是等价的二维表格写法每行首列置 1dp[i][j]继承上一行不用当前硬币并加上同行更小金额再用一枚当前硬币。复杂度分析时间复杂度O(n * a)空间复杂度O(n * a)方法四动态规划·空间优化滚动一维数组直觉观察 2D 递推式dp[i][a]只依赖两处下一行跳过硬币dp[i 1][a]当前行使用硬币dp[i][a - coins[i]]。因此每一行只与相邻行相关可以用两个一维数组滚动替代整张二维表空间降至O(a)。仓库中的 go/0518-coin-change-ii.go 正是这一思路的 Go 实现外层逆序遍历硬币nextRow[a] row[a]完成「跳过」的继承再叠加nextRow[a - coins[i]]完成「使用」的累加每轮处理完将row指向nextRow。算法步骤建立一维数组dp长度amount 1dp[a]表示用已处理的硬币组成金额a的方案数初始化dp[0] 1逆序遍历硬币新建nextDP并置nextDP[0] 1遍历金额a1到amount先继承dp[a]跳过当前硬币若a - coins[i] 0累加nextDP[a - coins[i]]再用一枚当前硬币处理完当前硬币后dp nextDP全部处理完dp[amount]即答案。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: dp [0] * (amount 1) dp[0] 1 for i in range(len(coins) - 1, -1, -1): nextDP [0] * (amount 1) nextDP[0] 1 for a in range(1, amount 1): nextDP[a] dp[a] if a - coins[i] 0: nextDP[a] nextDP[a - coins[i]] dp nextDP return dp[amount]public class Solution { public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int i coins.length - 1; i 0; i--) { int[] nextDP new int[amount 1]; nextDP[0] 1; for (int a 1; a amount; a) { nextDP[a] dp[a]; if (a - coins[i] 0) { nextDP[a] nextDP[a - coins[i]]; } } dp nextDP; } return dp[amount]; } }class Solution { public: int change(int amount, vectorint coins) { vectoruint dp(amount 1, 0); dp[0] 1; for (int i coins.size() - 1; i 0; i--) { vectoruint nextDP(amount 1, 0); nextDP[0] 1; for (int a 1; a amount; a) { nextDP[a] dp[a]; if (a - coins[i] 0) { nextDP[a] nextDP[a - coins[i]]; } } dp nextDP; } return dp[amount]; } };Go、JavaScript、Kotlin、Swift、Rust 的实现见 articles/coin-change-ii.md其中 python/0518-coin-change-ii.py 的第三个版本即本方法的 Python 落地。Swift 与 Kotlin 版本额外加入了整数溢出防护Int.max检查、System.arraycopy回填。复杂度分析时间复杂度O(n * a)空间复杂度O(a)方法五动态规划·最优原地更新一维数组直觉既然「跳过」只是把旧值原样继承「使用」只是叠加同数组更小金额的值那么在正确的遍历顺序下可以直接在同一个一维数组上原地累加连滚动数组都省去dp[a]始终表示「用已处理过的硬币组成金额a的方案数」每个硬币只依赖「同金额的旧值」与「更小金额的新值」。关键在于外循环是硬币、内循环是金额——这一顺序同时保证了同一硬币可无限复用内层正向扫描时dp[a - coin]已包含当前硬币且不同组合不会因顺序重复计数。算法步骤建立一维数组dp长度amount 1dp[a]表示组成金额a的方案数初始化dp[0] 1逆序遍历硬币对每个硬币正向遍历金额a1到amount若coin adp[a] dp[a - coin]全部处理完返回dp[amount]。代码实现class Solution: def change(self, amount: int, coins: List[int]) - int: dp [0] * (amount 1) dp[0] 1 for i in range(len(coins) - 1, -1, -1): for a in range(1, amount 1): dp[a] dp[a - coins[i]] if coins[i] a else 0 return dp[amount]public class Solution { public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; for (int i coins.length - 1; i 0; i--) for (int a 1; a amount; a) dp[a] dp[a] (coins[i] a ? dp[a - coins[i]] : 0); return dp[amount]; } }class Solution { public: int change(int amount, vectorint coins) { vectoruint dp(amount 1, 0); dp[0] 1; for (int i coins.size() - 1; i 0; i--) { for (int a 1; a amount; a) { dp[a] dp[a] (coins[i] a ? dp[a - coins[i]] : 0); } } return dp[amount]; } };class Solution { /** * param {number} amount * param {number[]} coins * return {number} */ change(amount, coins) { const dp new Array(amount 1).fill(0); dp[0] 1; for (let i coins.length - 1; i 0; i--) { for (let a 1; a amount; a) { dp[a] coins[i] a ? dp[a - coins[i]] : 0; } } return dp[amount]; } }int change(int amount, int* coins, int coinsSize){ if (coinsSize 0) { return amount 0; } int* dp calloc((amount 1), sizeof(int)); dp[0] 1; for (int i 0; i coinsSize; i) { for (int j coins[i]; j amount; j) { dp[j] dp[j - coins[i]]; } } int ans dp[amount]; free(dp); return ans; }C、Rust、Kotlin 版本的实现都采用了「外层硬币、内层金额、正向扫描」的简洁形态c/0518-coin-change-ii.c 直接从j coins[i]起步规避负索引rust/0518-coin-change-ii.rs 用for i in c..n做相同的事并返回dp末元素kotlin/0518-coin-change-ii.kt 的第一版即最优一维解java/0518-coin-change-ii.java 的注释清晰标注了该解法的复杂度为O(n * amount)时间、O(amount)空间。复杂度分析时间复杂度O(n * a)空间复杂度O(a)五种方案对比速查方案核心思想时间复杂度空间复杂度1. 递归决策树跳过 / 使用指数搜索O(2^max(n, a/m))O(max(n, a/m))2. 自顶向下 DP递归 memo[i][a]记忆化O(n * a)O(n * a)3. 自底向上 DP2D 表格逆序填表O(n * a)O(n * a)4. 空间优化 DP滚动一维数组nextDPO(n * a)O(a)5. 最优 DP原地更新一维数组O(n * a)O(a)其中n为硬币种数a为金额m为最小硬币面额。方法 5 同时达到了 hint 文档要求的O(n * a)时间目标且空间进一步压至O(a)是面试与工程实践中的首选写法。常见陷阱陷阱一把组合数数成了排列数外层循环是金额、内层循环是硬币时[1, 2]与[2, 1]会被当成两种不同方案结果是排列数而非组合数# 错误数出的是排列数 for a in range(1, amount 1): for coin in coins: dp[a] dp[a - coin] # 正确硬币在外层数出的是组合数 for coin in coins: for a in range(coin, amount 1): dp[a] dp[a - coin]这正是本题与 0377 - Combination Sum IV排列计数金额在外层的本质区别。相关的组合计数题还包括 0039 - Combination Sum 与 0040 - Combination Sum II可与本题放在一起对照学习。陷阱二忘记初始化dp[0] 1dp[0]代表「金额 0 恰好有一种合法方式——一枚硬币都不选」。不初始化它所有金额的方案数都会是 0。这一边界在仓库的每一份实现如 go/0518-coin-change-ii.go 的row[0] 1中都得到了严格保留。陷阱三允许负数下标访问访问dp[a - coins[i]]前必须确认a coins[i]否则会造成负索引或越界错误# 错误可能访问负索引 dp[a] dp[a - coins[i]] # 正确先检查再访问 if a coins[i]: dp[a] dp[a - coins[i]]C 语言版从j coins[i]开始内层循环c/0518-coin-change-ii.cRust 版用for i in c..nrust/0518-coin-change-ii.rs都是从循环边界上根除这一隐患的做法。总结零钱兑换 II 是「完全背包 组合计数」的教科书级题目其解题链条非常清晰递归建立决策树心智模型每个状态只有「跳过」与「使用停在原地」两个分支记忆化消除指数级的重复子问题达到O(n * a)自底向上用 2D 表格复现同一递推去掉递归栈开销滚动数组 / 原地更新利用「行间依赖」将空间压到O(a)最终记住硬币在外层、金额在内层、正向扫描——这是组合计数的黄金三要素。本仓库为该题提供了 C、C、C#、Go、Java、JavaScript、Kotlin、Python、Rust、Swift、TypeScript 等多语言实现完整解法逐语言展开见 articles/coin-change-ii.md解题思路的渐进式提示见 hints/coin-change-ii.md各语言提交状态可对照 README.md 完成度表。掌握本题后可继续挑战 0322 - Coin Change求最少硬币数等变体进一步理解「计数」与「最优化」两类完全背包问题的异同。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考