1. 从一道“可以重复拿”的题目说起先搞懂完全背包和01背包差在哪在讲完全背包之前我默认你已经接触过01背包。如果还没看过建议先找一篇01背包的入门文章把状态定义搞明白因为完全背包就是在01背包的框架上改了“一个条件”但就是这一个条件把很多人的思路带偏了。我当年第一次做完全背包的时候心里想的是既然物品可以无限拿那我是不是要把每种物品复制成好多个然后当成01背包来做比如容量是10某件物品重量是3那我就复制3份或者4份然后再跑一遍01背包。这个思路不能说全错但属于“明明有电梯不走偏要爬楼梯”——能到但特别累而且稍不注意就会复制出问题。先看题目原型。假设有一个背包容量为C现在有N种物品每种物品的重量是w[i]价值是v[i]每种物品的数量是无限的。问在不超过背包容量的前提下能装下的最大总价值是多少注意关键词无限。这就是完全背包和01背包最本质的区别。01背包里每个物品你只有“拿”和“不拿”两个选择拿了就没了完全背包里每个物品你可以拿0次、1次、2次……一直拿到放不下为止。这个区别直接导致状态转移方程的变化。01背包的状态转移是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这里dp[i-1][j-w[i]]表示我在“前 i-1 个物品里做决定”的基础上再决定拿第 i 个物品。因为第 i 个物品只能拿一次所以拿到它之后前面只能是 i-1 个物品的决策结果。完全背包不一样我在决定要不要拿第 i 个物品的时候如果选择拿拿完之后我还是可以在前 i 个物品里继续做决定——因为我还可以再拿一次。所以状态转移变成dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])注意第二项从dp[i-1][j-w[i]]变成了dp[i][j-w[i]]。这个i和i-1的差别就是“能不能重复拿”的数学表达。去年我在公司带一个实习生他看完这两行方程之后问我“老师这不就差一个下标吗有这么重要吗”我说你别小看这个下标你把它写成一维数组跑一遍就知道差别有多大了。后面我会专门讲这个。另外还要提一下在日常的算法题和面试里完全背包最常见的两种考察形式是“最大价值问题”和“方案数问题”。最大价值就是上面说的那个模型方案数问题则是问“有多少种凑法”比如经典的“零钱兑换II”。方案数问题的转移方程只需要把max换成但初始化的方式会有一点变化后面我也会提到。接下来我把完全背包的完整解法拆成几步从二维dp开始讲讲完再优化成一维dp最后给几个常见变体和面试高频坑点。保证你看完能直接AC掉LeetCode上那几道经典题。2. 二维dp实现先把最朴素的思路写对2.1 状态定义和初始化先说状态定义。我们用dp[i][j]表示在前 i 种物品中任意选取每种物品可以选任意次放入容量为 j 的背包能获得的最大价值。这里一定要把“前 i 种物品”和“容量为 j”这两个维度理解透。前者是物品的维度后者是容量的维度。二维数组的两根轴一根管物品范围一根管背包容量缺一不可。初始化的时候dp[0][j]表示“在前0种物品里选”那任何容量下都选不出东西价值就是0。dp[i][0]表示“容量为0”那也什么都放不下价值也是0。所以整个二维数组初始化成全0就行不用额外处理边界。不过有一种情况需要特殊注意如果题目让你求的是“恰好装满背包”时的最大价值那初始化就不一样了。要把dp[0][0]设为0把dp[0][j]j0设为负无穷一般用-INF表示“容量没装满”这个状态是不可达的。这个细节很容易被忽略但真遇到了就是致命的。2.2 三层循环的朴素写法最直白但最慢的版本理解了状态定义之后最直观的写法反而不一定是两层循环而是三层循环——对每种物品枚举拿几个。伪代码如下// N是物品数量C是背包容量 // w[i]是第i种物品的重量v[i]是第i种物品的价值 // 物品编号从1开始 for (int i 1; i N; i) { for (int j 0; j C; j) { for (int k 0; k * w[i] j; k) { dp[i][j] max(dp[i][j], dp[i-1][j - k*w[i]] k*v[i]); } } }这个写法用了一个额外的k循环表示第i种物品拿k件。逻辑非常直白不拿就是k0拿1件就是k1拿2件就是k2……把所有可能都枚举一遍取最大值。但这样做的复杂度是 O(N * C * (C/w[i]))最坏情况下接近 O(N * C^2)数据量一大就挂了。比如背包容量是1000物品有100种最坏情况下的计算量就是亿级在LeetCode上大概率超时。所以三层循环这个版本我建议你只是用来验证小数据或者帮助自己理解“为什么完全背包是多阶段决策问题”。真正写题的时候要么用后面的二维优化写法要么直接用一维写法。2.3 去掉k循环的二维优化写法一个观察改变复杂度接下来要说的这个优化是理解完全背包的关键一步也是面试中经常被追问“为什么能这么优化”的点。仔细观察上面那个三层循环对固定的i和j我们要算的是max(dp[i-1][j], dp[i-1][j-w[i]] v[i], dp[i-1][j-2*w[i]] 2*v[i], ...)那如果我们已经知道了dp[i][j-w[i]]的值会怎样dp[i][j-w[i]]算的是max(dp[i-1][j-w[i]], dp[i-1][j-2*w[i]] v[i], dp[i-1][j-3*w[i]] 2*v[i], ...)发现没有dp[i][j-w[i]] v[i]恰好等于max(dp[i-1][j-w[i]] v[i], dp[i-1][j-2*w[i]] 2*v[i], dp[i-1][j-3*w[i]] 3*v[i], ...)这正好就是dp[i][j]中除了第一项dp[i-1][j]之外的所有候选值的最大值。于是退化到dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])就这么一个简单的数学观察把原来的三层循环降成了两层循环复杂度从 O(NC^2) 降到 O(NC)是质的飞跃。我举个例子帮助理解。假设当前物品重量w3价值v5背包容量j9。用三层循环的话你要枚举k0,1,2,3四种情况分别算价值0、5、10、15然后取最大值15。但是如果你已经知道了容量为6也就是j-w9-36时的最优解是10这个10可能来自拿了两件当前物品也可能来自前面的物品组合那你直接用10515就能拿到“拿一件当前物品之后继续在3容量里找最优”的结果。这比一个个试快多了。二维优化的完整代码for (int i 1; i N; i) { for (int j 0; j C; j) { if (j w[i]) { dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]); } else { dp[i][j] dp[i-1][j]; } } }答案是dp[N][C]。这个二维版本的空间复杂度是 O(N*C)比三层循环版写起来简洁思路也比较清楚。面试的时候如果你能把上面那段“观察”讲给面试官听基本能证明你是真的懂DP不是背模板。3. 一维优化为什么完全背包要正着遍历容量3.1 从滚动数组到一维dp空间复杂度降维打击二维dp的空间复杂度是 O(N*C)当 N 和 C 都很大时内存可能会爆。比如 N5000C5000那就是2500万个int约100MB多数在线判题系统会直接报MLE。于是我们需要空间优化。思路是这样的观察状态转移方程dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])发现dp[i][j]只依赖两个东西上一行的dp[i-1][j]以及本行的dp[i][j-w[i]]。如果我们在内层循环正着遍历j从 0 到 C那么在计算dp[j]的时候dp[j-w[i]]已经是本轮的更新结果了——这正是我们需要的dp[i][j-w[i]]。而dp[j]在被覆盖之前存的还是上一轮的dp[i-1][j]——这正好是方程里的另一项。所以一维写法非常简洁for (int i 1; i N; i) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j-w[i]] v[i]); } }注意内层循环是j从w[i]到C正着走。这个“正着走”就是完全背包和01背包在代码层面的分水岭。01背包一维写法是倒着走for (int i 1; i N; i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j-w[i]] v[i]); } }为什么01背包要倒着走因为dp[j-w[i]]必须是上一轮的结果不能是这一轮已经更新过的。如果正着走j从小到大递增dp[j-w[i]]很可能已经在当前物品的迭代中被更新过了这就等于“同一个物品被拿了多次”正好和01背包不允许重复拿的要求冲突。但完全背包恰恰需要“同一个物品可以被多次拿”所以正着走刚刚好。这个对应关系我建议你反复咀嚼几遍。之前有读者问我“老师如果我记反了比如完全背包写成倒序会怎样”答案是结果会变成“每种物品最多只能拿一次”也就是退化成01背包的结果了。如果你在做的是“零钱兑换”这类题目那答案就会错得离谱。还有一个坑初始化dp数组时如果求的是“恰好装满”的最大价值dp[0]应该设成0其他设成-INF。但如果求的是“不超过容量”的最大价值那全部初始化成0就行。两种初始化带来的结果差异在实际题目中非常容易踩雷。3.2 正序和逆序的直观理解用生活场景拆解一下很多教程会直接告诉你“01倒序完全正序”但不解释为什么。我换一个生活化的说法来解释。你可以把01背包想象成“超市限购”每种商品每人只能买一件。你在货架前从左往右逛这就像正序遍历如果看到一件商品便宜你放进购物车了再逛到更便宜的同款商品其实不存在因为限购你不会重复拿。但完全背包像是“不限量自助餐”每道菜你可以反复去拿。你从左往右走看到一个好吃的拿了一份走了两步觉得还能再吃回头又拿了一份。正序遍历恰好模拟了这种“拿了之后还可以再回来拿”的机制。反过来如果你倒着走从右往左每道菜你只看了一眼拿不拿就决定了不会回头这就是01背包。这个类比不算特别精确但对于刚开始接触DP的人来说能帮助建立直觉。等你写多了自然会理解到“正序和逆序的差别本质上是对状态依赖关系的控制”。3.3 对比表格01背包 vs 完全背包我把两者的关键区别整理成一个表格方便你在复习的时候一眼扫过去对比项01背包完全背包每种物品的选取次数最多1次无限次二维状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])一维内层遍历顺序j从大到小逆序j从小到大正序空间复杂度一维O(C)O(C)典型题目分割等和子集、最后一块石头的重量II零钱兑换、零钱兑换II、完全平方数“恰好装满”初始化方式dp[0]0, 其余-INFdp[0]0, 其余-INF如果你能把上面这张表完全理解而不是靠死记硬背那完全背包这块就过了大半关了。4. 经典例题实战拿LeetCode 322和518练手4.1 零钱兑换LeetCode 322求最小硬币数量题目是这样的给定不同面额的硬币和一个总金额写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。每种硬币的数量是无限的。这是一道非常标准的完全背包“最小价值”变体。为什么是最小价值因为它求的不是“最大总价值”而是“最少硬币数”。思路如下定义dp[j]表示凑成金额j所需的最少硬币数。初始化的时候dp[0] 0其他dp[j]设为一个很大的数比如INT_MAX或者amount 1。这里用amount 1有个好处——如果一个值永远是amount 1就说明这个金额凑不出来最后返回 -1 即可。状态转移dp[j] min(dp[j], dp[j - coin] 1)注意这里是min因为我们要最少的硬币数。核心代码int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] min(dp[j], dp[j - coin] 1); } } return dp[amount] amount ? -1 : dp[amount]; }这里有几个点需要确认一下第一dp[j]定义为“凑成金额j的最少硬币数”边界是dp[0]0表示凑0元需要0个硬币。第二内层循环从coin开始正序遍历因为硬币无限。第三返回的时候判断dp[amount] amount而不是dp[amount] INT_MAX是为了防止整数溢出。如果初始化用amount 1这个判断就特别安全。我之前有个学员特别喜欢把初始化的值设成INT_MAX然后转移的时候写dp[j] min(dp[j], dp[j - coin] 1)。如果dp[j-coin]是INT_MAX加1就溢出了变成负数直接污染结果。这就是为什么我建议用amount 1作为哨兵值。4.2 零钱兑换IILeetCode 518求凑成总金额的方案数这个题目和322非常像但问题从“最少需要几个硬币”变成了“一共有多少种凑法”。本质上是完全背包的“方案数”变体。状态定义dp[j]表示凑成金额j的方案总数。初始化dp[0] 1表示凑0元只有一种方案什么都不拿。其他dp[j]初始化为0。状态转移dp[j] dp[j] dp[j - coin]这是在枚举每个硬币面额时把“不使用当前硬币”的方案数原来的dp[j]和“使用当前硬币”的方案数dp[j - coin]加起来。核心代码int change(int amount, vectorint coins) { vectorint dp(amount 1, 0); dp[0] 1; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] dp[j - coin]; } } return dp[amount]; }这个代码有一个非常隐蔽的坑就是外层循环务必是硬币内层循环务必是金额。如果你把内外层交换了得到的结果会变成“排列数”而不是“组合数”。举个例子你就明白了。假设硬币面额是 [1, 2]总额是 3。组合数的话只有两种凑法111 和 12。但你如果把内层循环换成硬币外层是金额那相当于你要依次算“金额为1的所有硬币组合”“金额为2的所有硬币组合”……这样12和21会被当成两种不同的方案结果就是3。这正是很多人写这道题WAWrong Answer的原因。顺便提一句如果题目要求“排列数”比如爬楼梯问题把不同顺序算作不同方案那就该把外层循环改成金额内层循环改成物品。这个细节对理解DP的“顺序敏感性”非常有帮助值得好好体会。4.3 完全平方数LeetCode 279不太像背包的背包题很多人的第一反应是“这题跟背包有什么关系”但它还真是完全背包只是换了个皮。题目给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n你需要让组成和的完全平方数的个数最少。在这个题里“物品”就是每个完全平方数i*i“背包容量”就是n“价值”就是1每选一个平方数个数加1。因为每个平方数可以重复选所以是完全背包。核心代码int numSquares(int n) { vectorint dp(n 1, INT_MAX); dp[0] 0; for (int i 1; i * i n; i) { int square i * i; for (int j square; j n; j) { dp[j] min(dp[j], dp[j - square] 1); } } return dp[n]; }这个题用完全背包的思路做时间复杂度 O(n * sqrt(n))完全够用。而且它比零钱兑换更简单一点因为物品序列是固定的从1到sqrt(n)的平方数根本不用自己去想有哪些物品。我为什么把这个题也列出来因为它很典型地展示了DP建模的思维方式把看似不是背包的题目转化为背包模型。面试的时候如果你能一眼识别出这种“披着羊皮的狼”会非常加分。5. 变体与延伸除了最大价值和方案数还有哪些考法5.1 完全背包求具体方案从“求值”到“求路径”前面讲的都是求最优值或方案数但有些题目会问你“把哪些物品放进了背包”。这种题属于“输出具体方案”的问题。一般的做法是先用DP算出最优值然后反向回溯。你从dp[N][C]开始如果dp[i][j] dp[i-1][j]说明第 i 种物品没拿如果dp[i][j] dp[i][j-w[i]] v[i]说明第 i 种物品拿了然后继续看dp[i][j-w[i]]。注意因为完全背包允许拿多次所以回溯的时候不是直接跳到i-1而是可能还要留在i这一行继续回溯。这个逻辑跟01背包略有区别。如果你用一维dp做完了想回溯方案就有点麻烦了——一维数组把“路径信息”丢了所以建议输出方案时用二维dp。5.2 多重背包与完全背包的边界一种物品最多拿k次怎么办这里顺带提一下多重背包因为初学者很容易把完全背包和多重背包搞混。多重背包是每种物品有一个数量上限k[i]不能无限拿。求解多重背包的朴素做法是把每种物品拆成k[i]个独立的01背包物品复杂度较高。更优的做法是利用二进制拆分把k[i]拆成1, 2, 4, ..., 2^m, rest几个部分每个部分当作一个01背包物品。这个技巧在竞赛中很常见但面试里考察频率不如完全背包高。如果面试官问你“能不能把多重背包转成完全背包”你直接说“不能因为数量上限限制了重复拿取次数这和完全背包的无限次有本质区别”就足够展示你对这个知识点的理解深度了。5.3 完全背包的适用场景从算法题到实际工程虽然我们讨论的是算法题但完全背包的思想在实际工程中也有不少应用场景。举几个例子预算分配假设你有一个总预算有多个项目每个项目可以投入任意金额对应无限次选择求收益最大化的投入方案。这就是一个标准的完全背包问题。资源调度在云计算中资源池里有多种规格的虚拟机每种规格可以按需启动目标是在满足总资源需求的前提下最小化成本——这个建模思路和完全背包高度相似。切割问题有一根长度为 L 的钢管可以按不同长度切割出售每种长度的价格不同不限切割次数问最大收益。这是一个非常经典的完全背包变体长度就是物品重量价格就是价值钢管总长就是背包容量。我在实际工作中遇到过类似的场景虽然是业务需求而不是算法竞赛题但底层的DP建模逻辑完全一致。这也说明掌握DP不是单纯为了刷题它对培养“把现象问题抽象成数学模型”的能力帮助很大。6. 常见问题与排查技巧这些坑我全都踩过6.1 遍历顺序写反了正序写成逆序逆序写成正序这是完全背包里最常见的错误。症状是小数据测试用例能过但大数据WA。检查方法很简单你拿一个只有一件物品、重量为1、价值为2、背包容量为5的例子跑一遍代码。如果答案是10说明正序写对了如果答案是2那很可能是写成逆序了退化成了01背包。我的习惯是在写完DP循环后先用笔在纸上模拟一遍只有一件物品的情况确认结果符合“无限次取”的预期再去跑大用例。这个小习惯帮我省了很多debug时间。6.2 状态定义不清晰导致初始化错误很多人在做“恰好装满”类题目时初始化还是全0结果答案比预期小或者出现奇怪的数字。“恰好装满”的初始化规则我再说一遍dp[0] 0其余的设为-INF求最大值或者INF求最小值。只有这样才能保证“从容量0逐步装满”这个状态是合法路径其他未装满的状态都是非法路径。如果你是用一维dp注意初始化向量的时候要显式指定填充值不要默认用0。C的话就是vectorint dp(C1, -1e9)Java就是int[] dp new int[C1];然后循环填充-INFPython就是dp [float(-inf)] * (C1)。6.3 下标越界和物品顺序问题有些人在写内层循环时直接从j 0开始遍历然后在转移方程里加一个if (j w[i])判断。这样做是对的但要注意如果不加判断就直接访问dp[j-w[i]]当j w[i]时下标为负直接越界。另外在“组合数”问题中物品顺序不能颠倒。我说的是两层循环的嵌套顺序——外层必须是物品内层必须是容量。你要是写反了就会把组合数算成排列数。这个问题在“零钱兑换II”里特别容易出现代码看起来一模一样就是两层循环换了个位置结果天差地别。6.4 用int溢出导致结果错误在方案数类问题中如果题目说“结果可能很大请对 10^9 7 取模”那你在转移方程里就要每一步都取模。如果忘了取模或者在最后才取模中间就已经溢出答案直接错。在求最小值的题目里用INT_MAX做哨兵值时转移方程里千万别直接dp[j-coin] 1因为INT_MAX 1会变成负数反而比dp[j]小导致 min 结果全是负数。这是我反复强调的一点也是很多人在LeetCode 322上卡住的原因之一。以下是FAQ速查表我自己在复习时会过一遍症状可能原因解决方式完全背包结果等于01背包结果内层循环写成了逆序改成从w[i]正序遍历到C方案数偏大内外层循环顺序写反外层物品内层容量最小值答案是负数或异常小INT_MAX 1溢出用amount 1或1e9做哨兵“恰好装满”结果不对初始化全是0dp[0]0其余-INF或INF下层循环数组越界没有判断j w[i]内层循环从w[i]开始6.5 动态规划题目通用的自测方法最后分享一个通用的自测方法写DP题一定要先写小规模暴力解再用DP解去对拍。我刷题早期吃过很多亏觉得自己DP思路没问题然后一提交就WA。后来学乖了简单题还好难题我先写一个递归暴力版本哪怕会超时保证它在小数据上是对的。然后拿DP的结果和暴力解在小数据上逐一比对一旦不一致马上就能定位是状态定义错了还是转移方程错了。这个方法对完全背包尤其有用因为三层循环的朴素版本在小数据上能跑正好可以作为参考答案。等你把二维优化和一维优化写好之后用同样的随机数据去对拍基本一盯一个准。7. 一点个人的做题体会完全背包这个知识点如果你只是为了应付面试把“完全背包正序、01背包逆序”记住就行。但我个人建议还是花点时间把转移方程为什么从dp[i-1]变成dp[i]琢磨清楚。因为动态规划的东西你靠记忆是背不完的——变体太多了今天是最大价值明天是最小数量后天是方案数大后天还可能叠加“恰好装满”“顺序敏感”等边界条件。只有把状态定义、转移来源、遍历顺序这三件事理解透碰到任何变体你都能自己推导出来。最后再送一个小技巧刷DP题的时候别只盯着AC试着用“手推状态转移表”的方式把每一步在纸上画一遍。比如完全背包拿两个物品、容量大概是6把dp数组从头到尾填一遍。这个过程看起来慢但真的能帮你建立肌肉记忆。我当年就是这么把DP的基础打牢的后来遇到很多复杂的背包变体基本都能举一反三。