最近在按计划刷力扣热题100Day37 这天的主题卡在了完全背包上。背包问题在动态规划里占了很大一块01背包和完全背包又是两个最基础的入门模型。如果你刷过「分割等和子集」「目标和」这类题应该对 01 背包的一维压缩写法比较熟。但完全背包的遍历顺序和状态转移推法跟 01 背包有明显差异理解不到位很容易把二维数组的 dp 写错或者在一维滚动数组上栽跟头。这篇文章就来捋一捋完全背包的底层逻辑以及怎么在 LeetCode 上找对应的经典题练手适合正在刷动态规划章节、尤其是卡在背包问题上的读者。Day37 这天我其实没刷太多新题主要干了一件事把完全背包的模板题零钱兑换 II、组合总和 IV、完全平方数、单词拆分统一过了一遍然后对比 01 背包重新推导了一遍状态转移方程。这个过程是值得记录的因为完全背包和 01 背包表面上只差了一个“每种物品是否可以重复取”但由此导致的遍历顺序、初始化方式、递推公式细节全都不太一样。很多刷题攻略不会把这些细节讲透只告诉你“完全背包正序遍历01 背包倒序遍历”但没解释为什么于是新手只能靠背。等到换一道题、包装一变立刻又不会了。我个人认为刷背包专题时不要只背模板要把下面三件事想清楚一是 dp 数组的下标定义和状态转移含义二是两层循环的内外层顺序对结果的影响三是一维滚动数组的更新方向在什么场景下成立。这三个问题搞明白后完全背包的整体框架就扎实了后面再刷其他背包变形多重背包、分组背包、树上背包都会顺很多。1. 完全背包的核心思路与题目识别1.1 什么样的题算完全背包先给一个最简单的模型有 N 种物品和一个容量为 V 的背包每种物品都有无限件可用。第 i 种物品的费用是 c[i]价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。对比 01 背包完全背包唯一的区别就是“每种物品无限件可用”即每件物品可以选择 0 次、1 次、2 次甚至更多次只要最终总重量不超过背包容量。这个“无限次使用”的性质直接导致了状态转移和遍历顺序的改动。在力扣上怎么快速识别一道题是不是完全背包我一般看两个特征题目中有明确的可重复选择的“物品”比如硬币面额可以重复使用、数字可以重复选取等。目标是“装满某个容量”或“达到某个目标值”比如凑出 amount、达成 target 正好等于某个值。经典题比如零钱兑换给定不同面额的 coins 和一个总金额 amount求组成 amount 的最少硬币数。零钱兑换 II求组成 amount 的硬币组合数。组合总和 Ⅳ求组成 target 的排列数。完全平方数给定正整数 n求最少可以拆分成多少个完全平方数之和。单词拆分给定一个字符串 s 和一个单词字典 wordDict判断 s 能否被拆分成若干个字典中出现的单词。以上几道题都是力扣热门题也都是完全背包的变体。如果你发现自己正在刷这些题那大概率就是在练完全背包。1.2 完全背包与 01 背包的状态转移对比先看二维 dp 的定义01 背包二维写法dp[i][j] 表示前 i 个物品放入容量为 j 的背包能获得的最大价值。状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j - c[i]] w[i])这里的关键是第 i 个物品只有“拿”或“不拿”两种选择。拿了之后前 i-1 个物品继续参与决策。完全背包二维写法dp[i][j] 表示前 i 种物品、容量为 j 时的最大价值。状态转移dp[i][j] max(dp[i-1][j], dp[i][j - c[i]] w[i])看出区别了吗完全背包在“拿第 i 种物品”的时候后续还能继续拿第 i 种物品所以不是 dp[i-1][j - c[i]]而是 dp[i][j - c[i]]。这一行就是完全背包与 01 背包在状态转移上唯一的本质区别。我个人建议你在纸上至少推导一遍这个二维数组。我第一次学的时候直接跳去背一维写法结果遇到变体题尤其涉及组合数和排列数时就露馅。二维推导一遍之后你会很自然地理解为什么一维解法里完全背包要正序遍历——因为 dp[i][j - c[i]] 在自己这一行更新往前推时需要同一个物品已经被放入多次正序遍历刚好满足这个语义。2. 一维滚动数组讲解与遍历顺序的深度解析2.1 为什么完全背包允许正序遍历在 01 背包的一维压缩写法中dp[j] 表示容量为 j 的背包能装的最大价值。更新代码一般是for (int i 0; i n; i) { // 遍历物品 for (int j V; j c[i]; j--) { // 遍历容量逆序 dp[j] max(dp[j], dp[j - c[i]] w[i]); } }为什么逆序因为 01 背包中每个物品只能选一次如果正序遍历容量dp[j - c[i]] 可能已经在本轮被更新过也就是第 i 个物品已经被放进去过了于是同一个物品会被重复使用这正好破坏了 01 背包的“每个物品最多一次”约束。但在完全背包中每个物品本来就可以用无限次所以反而不需要担心“同一个物品被重复使用”。于是遍历容量时改成正序for (int i 0; i n; i) { // 遍历物品 for (int j c[i]; j V; j) { // 遍历容量正序 dp[j] max(dp[j], dp[j - c[i]] w[i]); } }这一行改动就是一维解法里完全背包和 01 背包的所有区别。很多教程只给了结论但底层逻辑就是“重复使用是否合法”。合法就正序不合法就倒序。这里想再分享一个我的理解角度把滚动数组想象成一张 Excel 表格每一行是一个物品或者多种物品更新的过程。逆序遍历相当于每次更新都参考上一行上一个物品的数据保证当前物品不会重复正序遍历相当于在更新时允许参考当前行已经更新过的数据等于允许这个物品被反复叠加。这样一想遍历顺序就非常直觉了。2.2 组合数 vs 排列数内外层循环顺序怎么定完全背包一维写法还有一个很常考的细节把两层 for 循环的顺序换一下结果会从“组合数”变成“排列数”。先看力扣经典题零钱兑换 II。题中要求计算“可以凑成总金额的硬币组合数”这里不同顺序的硬币组合被视作同一种。比如 amount 5, coins [1, 2, 5]那么 122 和 212 视为同一种组合。这道题要求组合数所以正确的循环顺序是外层遍历硬币内层遍历金额。vectorint dp(amount 1, 0); dp[0] 1; for (int coin : coins) { for (int i coin; i amount; i) { dp[i] dp[i - coin]; } }为什么外层遍历硬币能得到组合数因为对于每一种硬币你先把这种硬币能组成的金额全部更新一遍等到你处理下一种硬币时之前那种硬币已经不会再参与排列了。这样12 和 21 不会同时出现因为处理 2 的时候前面的 1 已经确定不会在当前这一轮再改变相对顺序的组合了。再看组合总和 Ⅳ这道题求的是排列数顺序不同算不同。那么循环顺序就要反过来外层遍历目标值内层遍历 nums 中的每个数。vectorint dp(target 1, 0); dp[0] 1; for (int i 0; i target; i) { for (int num : nums) { if (i num) { dp[i] dp[i - num]; } } }这么写每次更新 dp[i] 时会尝试把任意一个 num 放在“最后一个位置”所以前面 target 为 i - num 的所有排列都被扩展到新的排列顺序自然被区分。这两道题是理解“组合数 vs 排列数”最好的对照题。我建议你刷的时候一定要把这两题放在一天做自己画一画 dp 数组的更新过程比看十篇解析都管用。不论你用的语言是 C、Java 还是 Python循环顺序这个点是完全通用的。3. 实操过程从零推导一道经典完全背包题3.1 力扣 322. 零钱兑换最少硬币数零钱兑换是很多人接触完全背包的第一道题。题面不复杂给定整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。接下来我不光讲思路我把自己的推导过程完整写一遍。先定义 dp[i] 表示凑出面额 i 所需要的最少硬币数量。初始化 dp[0] 0因为凑 0 元不需要任何硬币。其余 dp[i] 初始化为一个大数比如 INT_MAX / 2表示暂时不可达。状态转移时对于每个硬币面额 c如果 i c那么 dp[i] 可以由 dp[i - c] 1 转移来表示“在用掉一枚面值 c 的硬币后剩下的 i - c 元继续用相同种类的硬币凑”。因为我们求的是最少数量所以取 min。C 代码实现class Solution { public: int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, INT_MAX / 2); dp[0] 0; for (int i 1; i amount; i) { for (int c : coins) { if (i c) { dp[i] min(dp[i], dp[i - c] 1); } } } return dp[amount] INT_MAX / 2 ? -1 : dp[amount]; } };这段代码就体现了完全背包“物品无限用”的特征内层遍历硬币的时候硬币可以在同一轮里被多次选择。换个说法因为 dp[i - c] 可能已经包含了当前硬币的组合方式所以再放一枚当前硬币是允许的。也许你会问这里内外层循环的顺序有影响吗对于“求最小数量”这个目标函数其实内外层顺序对最终答案没有影响。因为 min 操作满足交换律无论是先遍历金额还是先遍历硬币最终每个 dp[i] 都会考察所有可能的最后一枚硬币。但如果题目问的是组合数就有影响这一点务必留意。Python 版本也很简单def coinChange(self, coins: List[int], amount: int) - int: dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! float(inf) else -1实测中这个二维顺序的写法在 LeetCode 上表现稳定。如果追求效率也可以把外层改硬币、内层改金额没有任何问题。3.2 力扣 279. 完全平方数完全平方数这道题表面包装不同但剥开就是完全背包。题面给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n你需要让组成和的完全平方数个数最少。这道题看起来跟硬币没关系但换个视角有一堆“物品”每个“物品”的价值是一个完全平方数 xx 的“花费权重”就是一个平方数问题变成了“组合出正好等于 n 的最小个数”。状态定义dp[i] 组成 i 所需的最少完全平方数个数。初始化 dp[0] 0其余设大数。C 写法一把平方数作为内层循环。class Solution { public: int numSquares(int n) { vectorint dp(n 1, INT_MAX / 2); dp[0] 0; for (int i 1; i n; i) { for (int j 1; j * j i; j) { dp[i] min(dp[i], dp[i - j * j] 1); } } return dp[n]; } };写法二先构造所有有可能用到的平方数集合背包外层遍历这些平方数内层遍历容量。class Solution { public: int numSquares(int n) { vectorint dp(n 1, INT_MAX / 2); dp[0] 0; for (int j 1; j * j n; j) { for (int i j * j; i n; i) { dp[i] min(dp[i], dp[i - j * j] 1); } } return dp[n]; } };两种写法都能过写法一更贴合“对每个目标值枚举最后一个平方数”写法二更贴合背包模板。我个人在初学完全背包时更建议用写法一因为它更直观不容易受内外层循环顺序的影响。到了后期熟练掌握“组合数 vs 排列数”之后再切换到标准背包模板。4. 常见问题与避坑经验实录4.1 初始化边界问题dp[0] 到底设多少这是完全背包最容易翻车的地方。dp[0] 的含义因题而异。求最大价值时dp[0] 0。求最少物品数量时dp[0] 0因为凑 0 不需要任何物品其他位初始化为一个大数。求组合数或排列数时dp[0] 1因为“凑出 0”有一种方案什么都不选。这个 1 是所有转移的起点。很多人在做零钱兑换 II 时把 dp[0] 初始化成 0导致所有答案全为 0。这类问题只要出现排查顺序一般先看初始化。4.2 用 INT_MAX 时注意溢出问题在求最小值时常会这样写dp[j] min(dp[j], dp[j - c[i]] 1);如果 dp[j - c[i]] 是 INT_MAX那么再加 1 就溢出成负数min 结果直接变成负数整份答案就崩了。所以我在代码里习惯用 INT_MAX / 2 或者 amount 1 这类足够大的数作为初始值而不是直接用 INT_MAX。这一点看似小但实际笔试或面试手写代码时经常踩。面试官不会像 LeetCode 那样给你一个固定的编译器提示稍不留神就写出溢出的逻辑调试半天发现是初始化的锅。4.3 组合数题别忽略内层循环的起点在零钱兑换 II 这类组合数题中内层循环要从 coin 开始而不是从 1 开始for (int i coin; i amount; i) { dp[i] dp[i - coin]; }如果你从 1 开始但加了 if (i coin) 的判断也没错只是多了一些无用的迭代。从可读性角度我更喜欢写 if (i coin) 的方式因为它更能表达边界条件。但从性能角度看直接让循环从 coin 开始更快且代码更简洁。这两种写法在竞赛中都可以接受关键是要理解循环起点背后的边界约束。4.4 内外面包顺序混淆导致排列组合错乱我在刷题群里见过很多朋友把零钱兑换 II 和组合总和 Ⅳ 的循环顺序搞反。其实有一个非常简单的记忆方法外层遍历物品硬币/数字内层遍历容量金额/目标值得到的是组合数。外层遍历容量内层遍历物品得到的是排列数。但这个方法仅适用于“求方案数”的场景。如果你在求最值比如最少硬币数内外层循环顺序通常不影响结果。理解这个微妙区别可以在面试时展现出你真的吃透了动态规划而不是背模板。4.5 完全平方数与单词拆分的“伪背包”包装完全平方数虽然能套背包模板但它的物品集合是动态生成的不是固定数组。如果你没意识到这一点容易在预处理物品数组时漏掉某些平方数导致答案错误。另一种更隐蔽的情况是有些平方数平方后超过 n却仍然进入了物品集合这会浪费计算时间但不影响正确性。单词拆分类似也需要把字典中的单词看作“物品”但字符串拼接和“容量”的关系并不像数值那么直观。这种题的转移条件不是简单的 i word.size()还要判断 s.substr(i - word.size(), word.size()) 是否等于 word。如果对这个条件不敏感套模板容易出 bug。我的建议是遇到这种包装题先别急着一股脑套背包模板先把“物品”和“容量”的映射关系在纸上写清楚再动手写代码。5. 刷题排布建议与进阶方向5.1 Day37 当天的题目安排参考我自己当天的刷题顺序是先花 30 分钟回顾 01 背包的一维写法重点观察倒序遍历的代码。再看完全背包的一维写法手动对比两个代码模板找出唯一的差异点。用零钱兑换 II 和组合总和 Ⅳ 做对照练习这两题的差异正好落在内外层循环上。做完全平方数和单词拆分巩固“物品可以无限使用”这个感觉。最后再回到 01 背包的经典题比如分割等和子集确认一下没有把两种模型记混。这套流程对我来说效率很高因为前后对比强烈知识点不容易遗忘。如果你当天时间有限至少要把零钱兑换 II 和组合总和 Ⅳ 这两题做完它们能验证你是否真的理解了完全背包的循环顺序。5.2 从完全背包延伸出去的进阶话题完全背包搞定之后刷题路上还会遇到多重背包和分组背包。多重背包是“每种物品有有限个数件可用”分组背包是“每组只能选一个”。这些模型在力扣上标注的题目不多但很多竞赛题和面试扩展题会用到。如果你的目标是面试而不是竞赛那么把 01 背包和完全背包吃透再掌握一两个变体比如带顺序的排列类问题基本就够用了。如果想深入竞赛可以再研究二进制优化、单调队列优化等技巧。我个人目前并没有一上来就啃优化算法的打算Day37 这天只求把完全背包的地基打牢。刷完这几道题之后我对“为什么正序、为什么交换内外层会影响组合排列”这个问题终于有了比较踏实的感觉不再像以前那样靠记忆硬撑。6. 写在最后的实操经验再分享一个小技巧做背包类题目时可以给自己准备一个“检查清单”每写一版代码后逐项核对dp 数组的长度是否有 1索引是否越界。dp[0] 的初始值是根据题目选 0 还是 1 还是大数。一维滚动数组写法里容量循环是正序还是倒序。如果拿不准先在纸上写二维递推再决定压缩成一维时要换向。求方案数时确认内外层循环顺序与“排列/组合”语义一致。求最小值时确认初始大数不会因为 1 而溢出。这个清单会随着你刷题积累不断扩展。到后期很多坑都是靠这种列表避免的而不是单靠经验。完全背包只是动态规划这条长路中的一小段但它串联了“无限选择”的一类问题理解透彻后很多看似花哨的题目都能映射到这个模型上。希望这篇笔记能帮你省下一点自己踩坑的时间。