零钱兑换 II（Coin Change II）：从递归决策树到一维 DP 的完整计数解法详解

零钱兑换 II（Coin 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 = 5，coins = [1, 2, 5]，答案为4，对应组合为：

• 5
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

这一描述可在仓库 cpp/0518-coin-change-ii.cpp 的注释中直接找到，仓库内该题的多语言解法均围绕这一语义实现（README.md 完成度表中列出了该题在 C、C++、C#、Go、Java、JavaScript、Kotlin、Python、Rust、Swift、TypeScript 等语言的提交情况）。

核心难点有二：

1. 硬币可无限复用——递归时不能简单跳到下一个索引，而要允许「停在当前索引继续取同一枚硬币」；
2. 组合而非排列——同样的硬币集合不能因顺序不同被重复计数，这直接决定了 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的方案数。

对硬币排序并始终沿列表向前移动，可以保证同一组合不会以不同顺序被重复统计。

算法步骤

1. 将硬币面额排序，保证顺序一致；
2. 定义递归函数dfs(i, a)：
   • i：当前硬币索引；a：剩余金额；
3. 若a == 0：返回1（形成一个有效组合）；
4. 若i越界（硬币耗尽）：返回0（无法组成）；
5. 初始化结果计数器res = 0；
6. 若当前硬币可用（a >= coins[i]）：
   • 分支一：跳过当前硬币 →dfs(i + 1, a)；
   • 分支二：使用当前硬币 →dfs(i, a - coins[i])（索引不变）；
   • 两者相加累入res；
7. 返回res；
8. 从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, vector<int>& coins) { sort(coins.begin(), coins.end()); return dfs(coins, 0, amount); } private: int dfs(const vector<int>& 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 3（hints/coin-change-ii.md）明确指出：这一方案是指数级的，必须想办法避免冗余计算。

---

方法二：动态规划·自顶向下（记忆化）

直觉

纯递归会反复求解同一批子问题。例如金额5、硬币[1, 2, 5]时，状态(i, a)会被大量重复访问。为此引入记忆化：每个状态由两个量唯一确定：

• 当前硬币索引i；
• 剩余金额a。

用哈希表或二维数组缓存memo[i][a]，命中即返回，避免重复计算（对应 hint 4 的建议：hints/coin-change-ii.md）。

算法步骤

1. 排序硬币；
2. 建立二维记忆表memo：memo[i][a]表示用索引i及其之后的硬币组成金额a的方案数；
3. 定义dfs(i, a)，与递归版本相同的语义；
4. a == 0→ 返回1；
5. i越界 → 返回0；
6. memo[i][a]已计算 → 直接返回缓存值；
7. 初始化res = 0；
8. 若a >= coins[i]：res = dfs(i + 1, a) + dfs(i, a - coins[i])；
9. 写入memo[i][a]并返回；
10. 从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, vector<int>& coins) { sort(coins.begin(), coins.end()); vector<vector<int>> memo(coins.size() + 1, vector<int>(amount + 1, -1)); return dfs(0, amount, coins, memo); } int dfs(int i, int a, vector<int>& coins, vector<vector<int>>& 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）则用map<pair<int,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的方案数。

算法步骤

1. 排序硬币；设n为硬币种数；
2. 建立(n + 1) x (amount + 1)的 DP 表dp；
3. 初始化边界：任意i都有dp[i][0] = 1（金额为 0 只有一种方式——不选任何硬币）；
4. 逆序遍历硬币索引i（n-1到0）；
5. 对每个i，遍历金额a（0到amount）：
   • 若a >= coins[i]：
     • 跳过当前硬币：dp[i + 1][a]；
     • 使用当前硬币：dp[i][a - coins[i]]；
     • 两者相加得dp[i][a]；
6. 答案为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, vector<int>& coins) { int n = coins.size(); sort(coins.begin(), coins.end()); vector<vector<uint>> dp(n + 1, vector<uint>(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[i+1][a]、Swift 中为防溢出的Int.max检查等）见 articles/coin-change-ii.md。仓库内 kotlin/0518-coin-change-ii.kt 的第二版实现是等价的二维表格写法：每行首列置 1，dp[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。

算法步骤

1. 建立一维数组dp，长度amount + 1：dp[a]表示用已处理的硬币组成金额a的方案数；
2. 初始化dp[0] = 1；
3. 逆序遍历硬币：
   • 新建nextDP，并置nextDP[0] = 1；
4. 遍历金额a（1到amount）：
   • 先继承dp[a]（跳过当前硬币）；
   • 若a - coins[i] >= 0：累加nextDP[a - coins[i]]（再用一枚当前硬币）；
5. 处理完当前硬币后，dp = nextDP；
6. 全部处理完，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, vector<int>& coins) { vector<uint> dp(amount + 1, 0); dp[0] = 1; for (int i = coins.size() - 1; i >= 0; i--) { vector<uint> 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]已包含当前硬币），且不同组合不会因顺序重复计数。

算法步骤

1. 建立一维数组dp（长度amount + 1）：dp[a]表示组成金额a的方案数；
2. 初始化dp[0] = 1；
3. 逆序遍历硬币；
4. 对每个硬币，正向遍历金额a（1到amount）：
   • 若coin <= a：dp[a] += dp[a - coin]；
5. 全部处理完，返回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, vector<int>& coins) { vector<uint> 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. 自底向上 DP	2D 表格逆序填表	O(n * a)	O(n * a)
4. 空间优化 DP	滚动一维数组nextDP	O(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] = 1

dp[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.c），Rust 版用for i in c..=n（rust/0518-coin-change-ii.rs），都是从循环边界上根除这一隐患的做法。

---

总结

零钱兑换 II 是「完全背包 + 组合计数」的教科书级题目，其解题链条非常清晰：

1. 递归建立决策树心智模型：每个状态只有「跳过」与「使用（停在原地）」两个分支；
2. 记忆化消除指数级的重复子问题，达到O(n * a)；
3. 自底向上用 2D 表格复现同一递推，去掉递归栈开销；
4. 滚动数组 / 原地更新利用「行间依赖」将空间压到O(a)；
5. 最终记住硬币在外层、金额在内层、正向扫描——这是组合计数的黄金三要素。

本仓库为该题提供了 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