刷代码随想录刷到Day35动态规划part4我终于和背包问题短兵相接了。如果你也在跟这套训练营前面的斐波那契、爬楼梯、不同路径、整数拆分基本都是在帮你建立“dp数组怎么定义、递推公式怎么找”的直觉。但背包问题一上来就直接把状态数组从一维拉到了二维很多人在这一步开始掉队。今天这篇我把自己啃01背包和完全背包的过程、代码模板、以及踩过的坑全部摊开讲重点说清楚为什么遍历顺序会决定结果是组合数还是排列数、为什么一维dp必须倒序更新这类关键问题。内容不涉及花哨技巧就是把动态规划里这个高频考点的底层逻辑彻底盘明白。1. 背包问题动态规划里绕不开的那座山1.1 为什么Part4从这里开始切入动态规划前面的题目其实有一个共同点dp数组的下标通常只需要一个维度。比如爬楼梯dp[i]只依赖于dp[i-1]和dp[i-2]不同路径虽然用了二维数组但dp[i][j]的推导依然是走一步、再走一步的思维。到了背包问题这里状态的含义突然变成了“前i件物品放进容量为j的背包”这一下就把“二维状态的DP”这个能力缺口补上了。你仔细想背包问题和前面那些题最大的不同在于它不是从一个点走到另一个点而是要在“选”和“不选”之间做取舍。这就逼着我们去思考dp数组的每一个格子到底代表什么、上一层状态如何迁移到下一层。一旦这套思维建立起来后面那些看似无关的题目——分割等和子集、目标和、零钱兑换——都会自动归位到同一个框架里。这也是为什么代码随想录把背包问题放在动态规划part4因为它是从“会套模板”到“真正理解动态规划”的分水岭。1.2 先把背包家族分个类别一上来就晕背包问题在面试和刷题里最常见的四个类型是01背包、完全背包、多重背包和分组背包。其中01背包是所有变体的祖宗完全背包只需要把遍历顺序倒过来就会得到截然不同的语义。我做了个表格把你至少需要认识的这几类先放这里背包类型每个物品可取次数遍历顺序关键点典型题目01背包0次或1次内层容量倒序遍历分割等和子集、最后一块石头的重量II完全背包无限次内层容量正序遍历零钱兑换、完全平方数多重背包有限次拆成01背包处理携带矿石资源等题分组背包每组最多选一个先遍历组再遍历容量分组背包模板题如果你能把01背包和完全背包吃透剩下两类本质上都是“套壳”。多重背包就是把每件物品拆成多件不同的01背包物品分组背包也只是在01背包外面加了一层“组”的循环。所以在day35这个节点我会把核心精力集中在01背包和完全背包上你后面学起来会轻松很多。2. 手撕01背包从二维dp到滚动数组2.1 先看题目原型再谈dp数组含义01背包最经典的原型题是这样有n件物品每件物品有自己的重量weight[i]和价值value[i]现在有一个容量为bagSize的背包每件物品只能取一次问能装下的最大总价值是多少。我建议先定义二维dp数组因为这样语义最清晰dp[i][j]表示“从下标为0~i的物品里任意取放进容量为j的背包能得到的最大价值总和”。这里的i表示物品范围j表示背包容量。只要这个定义想清楚后面所有推导都会顺。很多教程喜欢直接给一维写法但我觉得新手一开始就直接用滚动数组非常容易懵。你根本不知道它在滚什么。所以我的建议是第一遍老老实实写二维理解透了再压缩成一维。面试的时候直接写一维没问题但你自己刷题阶段最好先把二维走一遍。2.2 递推公式是从“拿”和“不拿”里长出来的对于第i件物品你只有两种选择不把它放进背包那最大价值就是dp[i-1][j]意思是前i-1件物品在容量j下已经达到的最优解。把它放进背包那么你需要腾出weight[i]的空间也就是dp[i-1][j-weight[i]] value[i]。注意这里一定是dp[i-1]而不是dp[i]因为每件物品只能用一次你不可能在计算当前物品时已经把它算了一遍。所以递推公式就是dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])用个生活化的类比你出门只能带一个20寸登机箱里面有若干东西每件占的体积不同、带来的幸福感也不同。你碰到一件新东西时要么不带维持原计划要么把里面某件东西拿出来、给它腾位置dp[i-1][j-weight[i]]然后加上它的幸福感。这正是背包问题“状态转移”的全部秘密。2.3 初始化、遍历顺序二维dp中这些都可以很自由二维dp有一个让新手安心的点遍历顺序几乎不影响结果。因为dp[i][j]只依赖左上方的格子不管你是先遍历物品还是先遍历背包只要递推公式没写错最终答案都一样。这点和一维dp完全不同后面我会专门讲。初始化时dp[0][j]那行要单独处理因为第0件物品只能决定“放它”或“不放它”。如果物品重量小于等于背包容量它的价值就是value[0]否则就是0。我写一个完整的Python实现def zero_one_bag(weight, value, bag_size): n len(weight) # dp[i][j] 表示前 i 件物品装入容量 j 的背包的最大价值 dp [[0] * (bag_size 1) for _ in range(n 1)] for i in range(1, n 1): w, v weight[i - 1], value[i - 1] for j in range(1, bag_size 1): if j w: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][bag_size]你说为什么不用二维的“先物品后容量”循环顺序再纠结一遍因为在这个写法里每一行dp[i]只依赖dp[i-1]整行所以只要保证第i行用到的dp[i-1]行已经算完就行其他顺序无所谓。我习惯把物品放外层、容量放内层因为这样写最贴近“逐个考虑物品”的直觉。等你看完下一节的一维优化就会意识到这个直觉有多重要。2.4 一维dp滚动数组到底滚掉了什么当你理解了二维写法之后你会注意到一个事实dp[i][j]只用到dp[i-1][...]那一行更早的行根本不再需要了。那为什么还要开一个n1行的二维数组完全可以用一行数组原地滚动更新。这就是滚动数组的来历。一维递推公式长这样dp[j] max(dp[j], dp[j - weight[i]] value[i])这里的dp[j]在更新前表示上一层的状态更新后变成当前层的状态。麻烦就麻烦在如果你正着遍历jdp[j-weight[i]]可能已经被当前物品更新过了相当于同一件物品被放进了背包两次。这不是我们想要的01背包语义。所以必须倒序遍历def zero_one_bag_scroll(weight, value, bag_size): dp [0] * (bag_size 1) for i in range(len(weight)): w, v weight[i], value[i] # 倒序是灵魂保证每个物品最多被选一次 for j in range(bag_size, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[bag_size]我举一个能立刻看出差异的例子假设背包容量是4现在有一个物品重量是1、价值是15。如果正序遍历容量j1时dp[1]15j2时dp[2]max(0, dp[1]15)30j3时dp[3]max(0, dp[2]15)45j4时dp[4]60。可这是同一件物品它最多只能被装一次正确答案应该是15。倒序遍历就不会出这种问题因为每次计算时dp[j-w]还停留在上一层的值。你现在应该彻底理解为什么01背包的内层循环必须从大到小跑了。3. 完全背包一行代码之差结果天壤之别3.1 完全背包每件物品可以无限次取完全背包和01背包的唯一区别是每件物品可以取无限次。这么一改代码上只需要把内层容量循环从倒序改成正序你就可以放心地让同一件物品被重复利用了。def complete_bag(weight, value, bag_size): dp [0] * (bag_size 1) for i in range(len(weight)): w, v weight[i], value[i] # 正序遍历允许一件物品被反复放进背包 for j in range(w, bag_size 1): dp[j] max(dp[j], dp[j - w] v) return dp[bag_size]如果你对比01背包的一维代码会发现只有range的方向变了。但你别小看这一行它背后的语义变化非常大正序遍历时你每次看到dp[j-w]都可能是本次放入物品之后的新状态也就是说当你计算容量更大的背包时前面的更新会继续参与一件物品就可以被多次累加进去。这就是完全背包的核心机制。如果用自助餐来类比01背包就像点套餐每道菜只能点一次完全背包就像自助餐厅取完还可以再去取。代码区别就藏在“还能不能再取一次”这件事上。3.2 求组合数还是排列数全看外层和内层谁先谁后这里我要讲一个面试里特别爱问、也特别容易让人糊涂的点完全背包求“装满背包有多少种方法”时内外层循环顺序决定了结果是组合数还是排列数。先给结论外层遍历物品、内层遍历容量得到的是组合数。也就是说{1, 2}和{2, 1}算同一种方案。外层遍历容量、内层遍历物品得到的是排列数。也就是说{1, 2}和{2, 1}算两种不同方案。原因很简单。外层遍历物品的时候你在每一轮只考虑当前这个物品和它以前出现过的物品不会回头考虑后面的物品所以先后顺序被固化了自然就是组合。而外层遍历容量的时候你每一轮都在所有物品里重新挑选先选1还是先选2都会被独立记录顺序不同就算不同于是变成排列。我习惯用一个简单口诀记要求顺序无关就把物品放外层要求顺序相关就把容量放外层。这个判断在实战中极其好用能省下大量纠结的时间。3.3 三个经典题直接套模板零钱兑换II、组合总和IV、最少硬币数我们还是用代码说话。第一个是零钱兑换II求凑出amount的硬币组合数。def change(amount, coins): # dp[j] 表示凑出金额 j 的组合数 dp [0] * (amount 1) dp[0] 1 # 空集是一种组合 for coin in coins: for j in range(coin, amount 1): dp[j] dp[j - coin] return dp[amount]这里dp[0]1是因为凑出金额0时什么都不选就是一种方案。如果没有这个初始化后面所有加法都会从0开始结果永远算不出来。这也是背包问题里初始化最容易踩的坑之一。第二个是组合总和IV它和零钱兑换II几乎一模一样只是求的是排列数。def combination_sum4(nums, target): dp [0] * (target 1) dp[0] 1 # 外层先遍历容量内层遍历物品得到排列数 for j in range(1, target 1): for num in nums: if j num: dp[j] dp[j - num] return dp[target]你看代码差别只有两层循环的先后顺序。但前者返回的是组合数后者返回的是排列数。这个知识点几乎每年面试都会被拿出来考一定要亲手敲一遍把结果跑出来对比一下。第三个是零钱兑换也就是热词里常说的“动态规划最少硬币”问题。它要求用最少的硬币数凑出amount如果凑不出来返回-1。def coin_change(coins, amount): # dp[j] 表示凑出金额 j 所需的最少硬币数 dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): if dp[j - coin] ! float(inf): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这个题里初始化成无穷大是关键。因为求最小值如果用0当初始值那么min(0, x1)永远等于0结果全错了。无穷大表示“当前金额还没法凑出来”只有能凑出来时才参与状态转移。这里我还特意加了一个判断防止dp[j - coin]还是无穷大时再加上1导致数值异常。这个习惯看起来小但实战中能帮你避免不少诡异结果。4. 面试真题里的“伪装背包”怎么一眼识破4.1 不是所有背包题都长着背包的样子刷到这你会发现面试真正考你的不是“这是01背包吗”而是“你能否看出来这道题实际上是个背包问题”。经典的伪装题目至少有这几道分割等和子集、最后一块石头的重量II、目标和、一和零。它们没有一个在题目里提到背包两个字但解法全都可以套背包模板。怎么识别我有一个很实用的思路题目里如果出现了“从一堆东西里挑选每个东西只能用一次且某个容量/目标有上限”十有八九是01背包的变体。如果“可以用无限次”那就往完全背包靠。如果结果是“能不能凑出某个值”大概率是背包可行性问题如果是“有多少种办法”就是背包方案数问题如果是“最大能装多少”就是最值问题。这个判断流程一出来题目基本就拆掉一半了。4.2 分割等和子集能不能把数组分成两半分割等和子集的题目要求是给定一个只包含正整数的非空数组判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。如果一个数组能分成两个和相等的子集那说明整个数组的总和必须是偶数并且每个子集的和等于total/2。这样问题就变成能不能从数组里选出若干个数使它们的和恰好等于target total/2。每个数只能用一次这就是标准的01背包可行性问题。def can_partition(nums): total sum(nums) if total % 2 1: return False target total // 2 dp [0] * (target 1) for num in nums: for j in range(target, num - 1, -1): dp[j] max(dp[j], dp[j - num] num) return dp[target] target这个写法里我把每个数字既当作重量又当作价值最后如果dp[target]等于target说明背包刚好装满。你也可以用布尔数组来写但用价值等于数字本身的做法可以直接复用前面所有01背包的模板思考成本最低。4.3 目标和、石头问题全是同一个模板的亲戚最后一块石头的重量II本质上也是把数组分成两堆让两堆和尽量接近。因为最后一块石头的重量等于两堆重量差的绝对值所以问题变成了在不超过total/2的前提下从数组中选一些数字使它们的和尽量接近total/2。这就是01背包求最大价值价值还是数字本身代码和分割等和子集几乎相同只是返回值从dp[target]target改成返回total - 2 * dp[total//2]。目标和这道题稍微绕一点给每个数字前面加上或-号使最终表达式的结果等于target问有多少种方案。假设所有正数的和是P所有负数的绝对值之和是N那么P - N targetP N total所以P (total target) / 2。问题就变成了从数组里选一些数字让它们的和恰好等于P求方案数。注意这里要求的是“方案数”所以dp[0]1外层物品内层容量组合数模板直接套。def find_target_sum_ways(nums, target): total sum(nums) if (total target) % 2 1 or abs(target) total: return 0 bag (total target) // 2 dp [0] * (bag 1) dp[0] 1 for num in nums: for j in range(bag, num - 1, -1): dp[j] dp[j - num] return dp[bag]我特别想强调的一点是这四道题表面完全不同但只要识破了“从n个元素中选若干个每个选一次目标是某个和/容量”这个共性就可以用同一套01背包模板五分钟内解决。这就是你在day35这个节点真正要练的能力。5. 实操踩坑实录这些坑我劝你别再踩一遍5.1 dp[0]到底等0还是等1背包问题里dp[0]的初始化几乎决定整道题能不能跑对。求最大价值、可行性时dp[0]通常为0求方案数时dp[0]必须为1因为“什么也不选”代表一种方案。我见过很多人在目标和、零钱兑换II这种求方案数的题里把dp[0]初始化成0结果整个dp数组全是0排查半天才发现是这个细节的锅。5.2 遍历顺序写反结果翻倍或者变成排列数这是背包问题里最容易翻车的地方。01背包内层容量必须是倒序完全背包是正序求组合数时外层物品、内层容量求排列数时外层容量、内层物品。如果写反了最常见的结果是01背包的答案偏大相当于物品被重复取或者把组合数题做成了排列数。我的排查方法很笨但很有效先用小规模样例把dp数组完整打印出来对照题目结果看看是不是第一轮循环就开始异常。5.3 滚动数组丢失中间状态调试时要学会“降维”一维数组写起来爽但调试时看不到二维的完整状态很多问题会被掩盖。我的建议是如果一维写出来结果不对立刻退回二维实现把每一行dp都打印出来逐行对照递推公式。确认二维版本没问题之后再机械地压缩成一维。不要觉得退回二维是浪费时间实际上这才是定位问题的最高效方式。我自己刷这部分的时候deliberately特意做了个小实验同一道01背包题分别用二维、一维、以及错误的正序一维各跑一遍然后把三个版本的结果和dp数组打印出来对比。结果非常直观——错误版本里同一物品的价值被累加了好几次。这个实验做完后我再也没有忘记过遍历顺序。5.4 零钱兑换类问题最怕你在无效状态上做加法最后一个高频坑在完全背包求最小值的题里如果用float(inf)初始化那么状态转移时要先判断dp[j - coin]是不是无穷大。不过Python里float(inf) 1不会报错只是变成了一个更大的浮点数最终min比较时不会影响结果所以有些情况下不判断也没事。但在一些严格类型语言比如C里用INT_MAX初始化后直接加1会导致整型溢出变成负数然后min的结果就全是负数了。这个坑太经典了我建议你无论用什么语言都养成先判断的习惯。我把常见问题整理成一个速查表方便你刷题时快速定位异常现象可能原因解决办法01背包结果偏大内层容量写成正序改回倒序组合数题答案偏大外层容量、内层物品换成外层物品、内层容量方案数结果全是0dp[0]初始化为0改成dp[0]1最少硬币数结果异常无效状态参与了转移先判断再更新一维实现总是差几个值没有先用二维验证退回二维打印dp数组我现在回看Day35这段内容最大的体会是背包问题不是靠背模板解决的而是靠理解“状态”和“顺序”之间的关系。你一旦想通了为什么01背包要倒序、为什么组合数要把物品放外层那些题目就不再是一道道孤立的题而是同一个逻辑在不同场景下的投影。这也是为什么我把这篇文章的重点放在推导逻辑和踩坑记录上而不是简单罗列代码。后面如果你继续往下刷就会发现多重背包、分组背包、甚至混合背包本质上都是在01背包和完全背包这两个核心模板上做加法。把今天这些内容吃透动态规划的后半程你会走得轻松很多。