欢迎阅读 欢迎来到「零钱兑换」题解之旅本文将带你从“凑出指定金额的最少硬币数”这一实际需求出发深入理解完全背包求最小值的 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到n0表示不使用任何硬币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] INFj 0没有硬币可用时无法凑出任何正金额标记为不可达。代码中通过循环for (int j1; jamount; 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(vectorint 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 vectorvectorbool dp(n 1, vectorbool(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(vectorint coins, int amount) { int n coins.size(); const int INF 0x3f3f3f3f; // 一维滚动数组 dp[j]表示当前已考虑的部分硬币种类下凑成金额 j 的最少硬币数 // 初始时未考虑任何硬币仅金额0可达0枚其余不可达INF vectorint 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数组初始化时为什么通常用amount1或INT_MAX表示“不可达”如果初始化为-1会有什么麻烦硬币面额数组coins是无序的这对 DP 结果有影响吗是否需要先排序本题中每种硬币无限使用所以内层循环应该从小到大还是从大到小延伸挑战将本题要求改为凑成总金额所需的最多硬币个数每种硬币无限你的 DP 转移和初始化需要做哪些调整如果题目改成凑成总金额的硬币组合数即有多少种不同的选法而不是最少个数DP 数组的含义和转移如何变化对比本题与完全背包恰好装满的写法你能看出二者在初始化dp[0]0其余为不可达和转移minvsmax上的异同吗如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在DP 的道路上越走越稳早日攻克每一道难题下次见 ✨
