LeetCode 332：零钱兑换（动态规划/完全背包）—— 题解

发布时间：2026/7/18 19:38:20

👋 欢迎阅读

🎯 欢迎来到「零钱兑换」题解之旅！本文将带你从“凑出指定金额的最少硬币数”这一实际需求出发，深入理解完全背包求最小值的 DP 模型，并掌握不可达状态（INF）初始化的核心技巧。

在开始之前，建议你先：

了解题目背景：这是 LeetCode 322 题，给定若干种无限数量的硬币面额coins和目标金额amount，求所需的最少硬币个数；若无法凑出则返回-1。本质上，这是完全背包的最小价值变种（价值即为硬币个数）。
明确学习目标：掌握如何将“最少硬币数”转化为完全背包求最小值，理解二维 DP 表格的构建，以及正序遍历金额以允许同种硬币重复使用的关键原因，并熟练使用INF 初始化不可达状态。
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证每个示例（如coins = [1,2,5], amount = 11输出3）。

本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现，层层递进。即使你对完全背包还不熟悉，我们也会从 01 背包对比出发，让你轻松抓住核心思想——正序 vs 逆序的本质差异。现在，让我们一起凑出最少的硬币数，解开零钱兑换的 DP 密码吧！ 💰🔢

一、题目

322. 零钱兑换 - 力扣（LeetCode）

二、做题思路

问题转化（前置分析）

本题是典型的完全背包求最小值问题：每种硬币数量无限，目标是凑出总金额amount，求使用的最少硬币数。

背包容量 =amount
物品体积 =coins[i]
物品价值 =1（每枚硬币贡献 1 个数量）
目标：恰好装满容量amount的前提下，最小化总价值（硬币数量）
由于是求最小值，不可达状态用INF（大数）标记。

1. 状态表示（核心基础，包含推导思路）

为什么这样定义dp[i][j]？

我们需要记录处理到第几种硬币以及当前已经凑出的金额。
对于每种硬币，由于数量无限，可以选择 0 枚、1 枚、2 枚……，这符合完全背包的特征。
因此，定义dp[i][j]表示使用前i种硬币（coins[0..i-1]），凑出金额j所需的最少硬币数。
i范围0到n（0表示不使用任何硬币），j范围0到amount。
这个状态能覆盖所有前缀硬币和金额的组合，满足无后效性，是解决本问题的出发点。

2. 状态转移方程（关键难点）

对于第i种硬币（面额coins[i-1]），有两种决策：

不选：硬币数为dp[i-1][j]（继承上一行的结果）。
选（至少一枚）：前提是j >= coins[i-1]，硬币数为dp[i][j - coins[i-1]] + 1。
注意此处使用的是dp[i][...]而非dp[i-1][...]，因为完全背包允许重复选取当前硬币，dp[i][j - coins[i-1]]可能已经包含了当前硬币的多次使用，这体现了无限取用的特性。

3. 初始化（边界防护）

dp[0][0] = 0：不使用任何硬币，凑出金额0需要0枚硬币，可行。
dp[0][j] = INF（j > 0）：没有硬币可用时，无法凑出任何正金额，标记为不可达。
代码中通过循环for (int j=1; j<=amount; ++j) dp[0][j] = INF;实现，dp[0][0]保持默认0。
其余dp[i][j]初始化为0，但会在递推中被覆盖。

4. 填表顺序（递推方向）

dp[i][j]依赖上一行dp[i-1][j]和当前行左侧dp[i][j - coins[i-1]]，因此必须按行从上到下（i从 1 到n），列从左到右（j从 1 到amount）遍历。

为什么完全背包要正序（从左到右）？
因为完全背包允许无限次选取当前硬币，dp[i][j]需要利用同一硬币已更新过的较小金额状态dp[i][j - coins[i-1]]，即表示“已经选过一枚当前硬币后继续选”的累计数量。若采用逆序，dp[i][j - coins[i-1]]仍为上一轮状态，则每枚硬币最多被选一次，无法实现重复选取。
正序的具体作用：当j从小到大遍历时，dp[i][j - coins[i-1]]已经在本轮被更新过（因为j - coins[i-1] < j，先被处理），所以它包含了当前硬币的多次使用信息，从而允许无限取用。

5. 返回值（目标映射）

若dp[n][amount] == INF，表示无法凑出总金额，返回-1；否则返回dp[n][amount]，即为最少硬币数。

三、代码

class Solution { public: bool canPartition(vector<int>& nums) { // 1. 计算数组总和，若为奇数则不可能平分 int sum = 0; for (auto x : nums) sum += x; if (sum % 2 != 0) return false; int target = sum / 2; // 目标子集和 int n = nums.size(); // 2. 创建dp表 // dp[i][j] 表示能否从前 i 个元素中选取若干个数，使其和恰好为 j vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false)); // 3. 初始化 // 前 i 个元素中，选出和为 0 的方案总是存在（即什么都不选），所以 dp[i][0] = true for (int i = 0; i <= n; i++) { dp[i][0] = true; } // 4. 填表顺序：外层遍历物品（i 从 1 到 n），内层遍历容量（j 从 1 到 target） // 因为 dp[i][j] 依赖于 dp[i-1][j]（不选当前数）和 dp[i-1][j-nums[i-1]]（选当前数）， // 所以按行从上到下、列从左到右即可。 for (int i = 1; i <= n; i++) { for (int j = 1; j <= target; j++) { // 5. 状态转移方程： // 不选第 i 个数：继承上一行的状态 dp[i-1][j] // 选第 i 个数：前提是 j >= nums[i-1]，且 dp[i-1][j-nums[i-1]] 为 true dp[i][j] = dp[i - 1][j]; if (j >= nums[i - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]]; } } } // 6. 返回值：dp[n][target] 表示能否从前 n 个数中选出和为 target 的子集 return dp[n][target]; } };

四、流程图

五、优化

状态转移方程

对于当前硬币面额coin = coins[i-1]（第i种），决策为选或不选，但由于可重复选，一维转移为：
dp[j] = min(dp[j], dp[j - coin] + 1)（当j >= coin时）。
dp[j]左侧（等号右边）为上一轮（不选当前硬币）的值，即继承旧状态。
dp[j - coin]为本轮已更新的值，表示已经选过至少一枚当前硬币后，继续累加的数量，这允许无限次使用同一硬币。

填表顺序

外层循环遍历每种硬币（i从 1 到n），内层循环必须正序遍历金额j（从 1 到amount）。
为什么完全背包要正序（从左到右）？
因为完全背包允许无限次选取当前硬币，dp[j]需要利用同一硬币已更新过的较小金额状态dp[j - coin]，即表示“已经选过一枚当前硬币后继续选”的累计数量。
当j从小到大遍历时，dp[j - coin]已经在本轮被更新过（因为j - coin < j，先被处理），所以它包含了当前硬币的多次使用信息，从而允许无限取用。
若采用逆序（如01背包），dp[j - coin]仍为上一轮状态，则每个硬币最多被选一次，无法实现重复选取，结果错误。

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); const int INF = 0x3f3f3f3f; // 一维滚动数组 dp[j]：表示当前已考虑的部分硬币种类下，凑成金额 j 的最少硬币数 // 初始时未考虑任何硬币，仅金额0可达（0枚），其余不可达（INF） vector<int> dp(amount + 1, 0); for (int j = 1; j <= amount; j++) { dp[j] = INF; } // 外层遍历每种硬币，内层正序遍历金额（完全背包特性） // 正序使得 dp[j - coin] 在本轮已被更新过，允许同一种硬币无限次使用 for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) { if (j >= coins[i - 1]) { // dp[j] 保留旧值（不选当前硬币）， // 或从 dp[j - coin] + 1 转移（选一枚当前硬币，复用本轮更新） dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1); } } } return dp[amount] == INF ? -1 : dp[amount]; } };

🎯 闭幕

🎉 恭喜你完成了「零钱兑换」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

本题要求最少硬币个数，与完全背包求最大价值思路相似，但求的是最小值。请思考：dp数组初始化时，为什么通常用amount+1或INT_MAX表示“不可达”？如果初始化为-1会有什么麻烦？
硬币面额数组coins是无序的，这对 DP 结果有影响吗？是否需要先排序？
本题中每种硬币无限使用，所以内层循环应该从小到大还是从大到小？