企业官网建设流程全解析

1. 经典动态规划第二篇：从"会套模板"到"真懂状态"

如果你一路刷题刷到这里，大概率已经被背包问题折磨过几轮了。这个系列上一篇我们聊了动态规划的基础框架——斐波那契、爬楼梯、打家劫舍这类入门题，这些题的核心套路是"前i个位置怎么递推"，状态只有一维，转移方程基本一眼能看穿。但到了面试常考题的进阶阶段，动态规划的难度会上一个台阶，最大的变化就是：状态从一个维度变成两个维度，决策从"取或不取"变成"取几个"。

这篇文章聚焦的是面试中出现频率最高的动态规划进阶类型——背包问题家族。我先说个面试时的真实观察：很多候选人刷过背包九讲，能背出01背包的转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，但被问到"为什么一维数组要倒序遍历"的时候，直接卡住。面试官其实很看重这一点，因为倒序遍历不是背下来的规则，而是"状态定义本身逻辑推导出来的必然结果"。所以这篇文章不会只给你模板，我会把每个关键选择的"为什么"拆开揉碎，讲清楚。

这篇文章适合谁看？正在准备算法面试、刷LeetCode和牛客的求职者，尤其是那些已经刷完入门DP题、但对背包类问题还是似懂非懂的人。看完你会搞明白三件事：01背包一维优化的原理、完全背包和多重背包的代码差异点、以及面试中如何快速拆解背包变种题。

2. 动态规划的思维底子：状态定义决定一切

2.1 从"暴力枚举"到"填表"的思维转换

在讲背包问题之前，我必须先把动态规划的核心思维方式再压一遍。很多人在做DP题的时候习惯去背模板，但模板只能帮你对付原题，面试官稍微改一个限制条件，你就懵了。真正的思考路径应该是从暴力解出发，一步步推导出DP解。

拿01背包举例，题目描述是：有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，每个物品只能取一次（0次或1次），问能装入背包的最大总价值是多少。

如果暴力枚举，每个物品有"取"和"不取"两种状态，n个物品就是2^n种组合，你逐个计算所有组合的总重量和总价值，筛掉超重的，取最大价值。这个思路本身没错，但n到30就已经跑不动了。怎么优化？观察暴力枚举的过程，你会发现大量子问题是重复计算的——比如枚举完前5个物品的装法后，第6到第n个物品的决策完全不依赖前5个具体怎么装的，只依赖"当前已经占用了多少容量"。

这就是动态规划的切入点：把"决策到第几个物品"和"当前剩余容量"这两个要素从暴力枚举中抽出来，作为状态的两个维度，然后用填表的方式避免重复计算。理解了这个思路，你就明白为什么背包问题的状态是二维的——它本质上是在记录暴力搜索过程中每个中间节点的最优值，只是用表的方式存了下来。

2.2 四个要素：状态、转移、初始化、遍历顺序

很多教程讲DP喜欢直接给状态转移方程，然后甩一段代码。但我的经验是，一个DP解法真正难的不是方程本身，而是四个要素彼此咬合的关系。我面试别人时喜欢按这个顺序提问：状态定义是什么？转移方程怎么来的？初始化为什么是这个值？遍历顺序能不能换？

这四个要素的优先级是自上而下的。状态定义错了，后面全是错的；状态定义对了，转移方程就是"当前状态从哪些前置状态来"的枚举；初始化是边界条件的落地；遍历顺序是代码实现时保证"转移方程用到的值已经被算好"的手段。很多人在遍历顺序上翻车，根本原因是没想清楚转移方程依赖的格子，在当前遍历到的时候是不是已经填好了。

这个框架不仅能用在背包问题上，任何DP题都可以套。你拿到一道题，先想状态的两个维度分别代表什么，再想当前状态可能从哪些状态转移过来，然后处理边界，最后选遍历方向。这篇文章后面所有的题目拆解，都会围绕这四个要素展开。

3. 01背包全拆解：面试最高频的DP模型

3.1 二维DP版本：先解决"对不对"

第一步永远是先把正确的解法写出来，不要一上来就优化。01背包的二维DP版本，状态定义和转移方程如下：

• dp[i][j]：考虑前i个物品（下标从1到i），在背包容量为j时的最大总价值
• 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

第一个选项dp[i-1][j]表示不取第i个物品，那结果就等于前i-1个物品在容量j下的最优解；第二个选项dp[i-1][j-w[i]] + v[i]表示取第i个物品，那要先把容量j中腾出w[i]的空间给第i个物品，前i-1个物品只能使用剩下j-w[i]的容量，再加上第i个物品的价值。

这个转移方程怎么来的？用我前面说的思路，就是在枚举第i个物品的决策："取"带来什么后果？"不取"带来什么后果？两者取最大值。枚举完一个物品，后面的物品决策就不依赖前面具体选了哪些，只依赖剩余容量。这就是无后效性，DP能成立的前提。

代码写出来大概是这样的（我用Python，因为面试写起来快、可读性好）：

def knapsack_01_2d(n, C, w, v): # dp[i][j]: 前i个物品，容量为j的最大价值 dp = [[0] * (C + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(0, C + 1): # 不取第i个物品 dp[i][j] = dp[i-1][j] # 取第i个物品（前提是容量够） if j >= w[i-1]: dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]) return dp[n][C]

注意初始化：二维数组的dp[0][j]，也就是前0个物品，无论容量多少，最大价值都是0。这个初始化是"没有物品可选时，价值为0"的直观表达。所有行滚动更新时，天然从第i-1行推到第i行，不会出现覆盖还没用的格子的问题。

3.2 一维滚动数组：为什么必须倒序遍历

二维版本解决了问题，但空间复杂度是O(n*C)。面试官大概率会追问一句："能优化空间吗？"这时候就要上滚动数组。观察二维版本的转移方程，dp[i][j]只依赖dp[i-1][...]这一行，也就是说第i-1行之前的数据在算第i行时完全用不到，那我们就没必要保留整张表，用一个一维数组反复覆盖更新即可。

核心代码如下：

def knapsack_01_1d(n, C, w, v): dp = [0] * (C + 1) for i in range(1, n + 1): # 关键：容量从大到小遍历 for j in range(C, w[i-1] - 1, -1): dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]) return dp[C]

这里最关键、面试必问的一点：为什么内层循环要从C倒序遍历到w[i]？

答案是：因为一维数组在更新dp[j]的时候，dp[j]本身代表的是"前i-1个物品在容量j下的最优值"，而dp[j-w[i]]需要也是前i-1个物品的最优值。如果正序遍历，dp[j-w[i]]可能已经被当前第i个物品更新过了，那就变成了"同一个物品被取多次"——这恰好是后面要讲的完全背包的逻辑。

举个例子就明白了。假设背包容量C=5，当前物品重量w=2，价值v=3。正序遍历：先更新dp[2] = max(dp[2], dp[0] + 3) = 3，然后更新dp[4] = max(dp[4], dp[2] + 3)。问题出现了：这个dp[2]是刚被当前物品更新过的值，它里面可能已经包含了当前物品，于是dp[4]就可能等于"当前物品取了两次"的价值（先占2容量，再占2容量，价值加了两次）。可01背包每个物品只能取一次，这显然不对。

倒序遍历：先更新dp[5]，此时用到的dp[3]是上一轮（前i-1个物品）的旧值，没被污染；然后更新dp[4]，用到的dp[2]也是旧值；最后更新dp[2]。这样每个物品只被考虑一次，完美符合01背包的语义。

注意：面试时如果被问到"二维转一维，除了空间优化还有什么好处"，可以从代码简洁性和面试表达两个角度回答。但不要画蛇添足说时间也优化了——时间复杂度没有变化，仍然是O(n*C)。

3.3 一个容易忽略的细节：物品和容量的遍历顺序

01背包还有个容易被忽视的细节：外层循环是物品，内层是容量，那能不能交换两层循环的顺序？

我直接说结论：在01背包中，如果用了二维DP，交换两层循环的顺序通常也能得到正确结果，只是语义上别扭；但用了一维滚动数组优化后，外层遍历物品、内层倒序遍历容量，这个顺序是不能随便交换的。因为外循环每轮只引入一个物品，内层倒序遍历保证了这一轮更新不会影响本轮的其他更新（前面说过的"污染"问题）。如果两层循环交换，外循环变容量、内循环遍历物品，那么同一个容量下会同时考虑多个物品加入，直接破坏"每个物品最多取一次"的限制。

所以你在面试时可以说：一维优化版的01背包，物品循环必须在外面，容量循环必须在里面且倒序。这个回答既展示了编码熟练度，也体现了对循环语义的理解。

4. 完全背包和多重背包：背包家族的三兄弟对比

4.1 完全背包：物品可以取无限次

完全背包和01背包唯一的区别是：每个物品可以取无限次（只要容量装得下）。这个差异看起来很小，但对代码的影响是颠覆性的。

先说二维DP推导。完全背包的状态定义和01背包一样：dp[i][j]表示前i个物品在容量j下的最大价值。但状态转移方程发生了变化：因为第i个物品可以取多次，所以当前状态不只是"不取第i个"或"取1个第i个"两种选择，而是"取k个第i个"（k可以从0取到j//w[i]）。暴力写法是枚举k：

dp[i][j] = max(dp[i-1][j], max_{k>=1, k*w[i]<=j}(dp[i-1][j-k*w[i]] + k*v[i]))

但这个枚举k的复杂度是O(nCC)，太慢了。优化思路是：用递推关系消掉枚举。观察发现：

dp[i][j]取第i个物品的话，等价于dp[i][j-w[i]] + v[i]。为什么？因为取1个第i个物品之后，你面对的还是"前i个物品、容量j-w[i]"的子问题（第i个物品还能继续取），这就是"无限次取同一个物品"的核心语义。于是转移方程简化为：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

这里要注意：第二个选项dp[i][j-w[i]]用的是同一行的格子，也就是在容量更小的时候已经考虑过继续取第i个物品的情况了，这和01背包用dp[i-1][j-w[i]]完全不同。

再转成一维数组，你会看到神奇的事情：完全背包的内层循环恰好是正序的：

def knapsack_complete(n, C, w, v): dp = [0] * (C + 1) for i in range(1, n + 1): for j in range(w[i-1], C + 1): # 正序遍历 dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]) return dp[C]

为什么正序就对了？因为正序遍历的时候，dp[j-w[i]]可能已经包含当前物品，所以dp[j]可以往"多次取当前物品"的方向更新。这和01背包的倒序刚好相反。面试时如果能把"01倒序、完全正序"这个差异背后的原理讲清楚，面试官基本就认定你真的懂DP了，而不是背代码。

4.2 多重背包：物品有次数限制，怎么把复杂度降下来

多重背包是这么个问题：第i个物品最多能用c[i]次，问最大价值。它介于01背包（只能用1次）和完全背包（无限次）之间。

最直接的做法是枚举每个物品取了多少个，转移方程变成dp[i][j] = max(dp[i-1][j - k*w[i]] + k*v[i])，其中0 <= k <= c[i]且k*w[i] <= j。复杂度O(nCC)（严格说是O(nC平均c[i])），在面试题里基本会超时，需要优化。

多重背包最常用的优化是二进制拆分。核心思想：一个物品的c[i]个可用次数，可以拆成若干个"01背包物品"，每个拆分出来的物品重量是w[i] * (2^k)，价值是v[i] * (2^k)，把所有拆分后的新物品跑一遍01背包即可。为什么是2的幂？因为[1,2,4,...,剩余]这个组合能表示0到c[i]之间的任意整数，这是二进制表示的基本原理。举个例子，如果c[i]=10，可以拆成1、2、4、3（10-1-2-4=3）四个新物品，这四个数任意组合能覆盖0到10的所有整数。

代码实现如下：

def knapsack_multiple(n, C, w, v, c): new_w, new_v = [], [] for i in range(n): # 二进制拆分 k = 1 while k <= c[i]: new_w.append(w[i] * k) new_v.append(v[i] * k) c[i] -= k k <<= 1 if c[i] > 0: new_w.append(w[i] * c[i]) new_v.append(v[i] * c[i]) # 01背包跑一遍 dp = [0] * (C + 1) for i in range(len(new_w)): for j in range(C, new_w[i] - 1, -1): dp[j] = max(dp[j], dp[j - new_w[i]] + new_v[i]) return dp[C]

我来解释一下这段代码里几个值得注意的点：

• while k <= c[i]：从1开始，不断乘2，直到超过剩余次数。每次拆分出一个重量为w[i]*k、价值为v[i]*k的新物品。
• 最后if c[i] > 0处理剩余次数，比如10拆完1、2、4后还剩3，就拆一个"3个一起"的组。这3个一组要和1、2、4组合起来恰好覆盖到10。
• 拆分完成后，新物品的"取或不取"本质上就是在决定"原始物品取k个"这个决策，所以直接套01背包的模板就行。

注意：二进制拆分后物品数量从n变成了O(nlog(max(c)))级别，所以整体复杂度是O(n * log(c) * C)。这个优化在面试中属于进阶考点，如果面试官没主动问，可以在写完基础多重背包解法后主动提一句"如果用二进制拆分可以优化到O(nlog(c)*C)"，会加分不少。

4.3 三兄弟对比速查表

为了方便记忆和快速查阅，我把三种背包的核心差异整理成一张表：

这张表最底层的规律是：遍历顺序不是拍脑袋定的，而是由"转移方程依赖上一行还是同一行的值"决定的。01背包转移依赖dp[j-w]里不含当前物品的最优值，所以要保证它不被当前更新污染——倒序；完全背包转移依赖dp[j-w]里已包含当前物品的最优值，所以要用当前更新的结果——正序。把这个逻辑讲清楚，遍历顺序就不会记反。

5. 从经典模板到高频变种：面试题真正考你的地方

5.1 恰好装满：初始化方式的微调

背包问题最常见的一个变种是：要求恰好装满背包，而不是不超过容量。比如LeetCode 322题零钱兑换，问凑出amount金额需要的最少硬币数；LeetCode 416题分割等和子集，问能否选出若干数恰好等于总和的一半。

这类题和标准背包的差别在初始化上，这一点很多人踩坑。回顾标准背包，我们初始化所有dp[j] = 0，含义是"容量j下可以不装任何东西，价值为0"。但"恰好装满"的语义下，容量为0时恰好装满的方案是存在的（什么都不选，价值为0），但容量大于0时如果没有合法方案，应该初始化为负无穷（求最大值时）或正无穷（求最小值时），表示"目前无法恰好凑满"。

拿LeetCode 322举例子，dp[j]表示凑出金额j所需的最少硬币数。初始化dp[0]=0，其他dp[j]=float('inf')。这样在状态转移时，dp[j] = min(dp[j], dp[j-coin] + 1)，只有当dp[j-coin]不是无穷大时，dp[j]才能被更新为有效值。如果没有这个初始化，dp[5]可能被错误地更新成inf+1之类的垃圾值。

用暴力枚举类比：你枚举所有可能凑出金额j的组合，如果凑不出来，结果应该是"不存在"，而不是"凑了0个硬币"。初始化就是提前告诉DP表："除容量0外，其他容量目前都凑不满"。

注意：我见过候选人写恰好装满的题时，代码逻辑全对，就是初始化的正负无穷设置错了方向。求最小值用float('inf')，求最大值用float('-inf')，这个别看反了。

5.2 求方案数：加号变求和

另一个高频变种是求方案数。比如LeetCode 494题目标和，给你一个数组，每个数前面可以加正号或负号，问有多少种方法让最终结果等于target。如果你被背包的"最大价值"思维定式锁住，可能半天想不出来。但实际上这类题只是把转移方程里的max换成+而已。

具体来说，定义dp[j]表示"凑出数值j的方法数"，那么状态转移就是：dp[j] += dp[j - num]。含义是：当前数取正的话，要凑出j，前面得先凑出j-num，方案数是dp[j-num]；当前数取负的话，前面得先凑出j+num，方案数是dp[j+num]。

这里要注意的是遍历顺序和初始化：初始化dp[0]=1，因为凑出0只有一种方法——什么都不选。做完状态转移后，答案就是dp[target]（可能需要处理偏移量，因为负数下标不支持）。这类题目只要识别出"计数"两个字，就不应该继续套max/min模板，而是换成累加。

5.3 二维费用背包：状态多一个维度

还有一种变种是二维费用背包，背包限重的同时限体积。比如LeetCode 474题一和零，给你若干字符串，每个字符串里有若干个0和1，问在最多能用m个0和n个1的限制下，最多能选多少个字符串。

这类题的状态要从二维变成三维：dp[i][j][k]表示前i个物品，在0的容量为j、1的容量为k时的最大选择数。通常可以压缩成二维滚动数组：dp[j][k]，外层遍历物品，内层两个容量维度都要倒序遍历（因为压缩后要用旧值）。转移方程就是01背包的二维版：

for s in strs: zeros = s.count('0') ones = len(s) - zeros for j in range(m, zeros - 1, -1): for k in range(n, ones - 1, -1): dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1)

面试中遇到二维费用的变种，判断标准很简单：题目里同时出现两个独立限制条件（比如重量+体积、0的数量+1的数量），转移时就需要两个维度同时参与。

5.4 背包装物品还是装字数？识别变种的"换皮"套路

我来总结一个判断变种题型的方法：面试题经常把背包装进各种故事里，但底层状态定义万变不离其宗。怎么快速识别？看三个点：

• 题目问的是"最大价值/最小代价"还是"方案数"？——max/min还是求和
• 每个物品/元素能不能重复用？——决定01背包还是完全背包
• 有没有"恰好"的约束？——决定初始化的正负无穷

举个例子，LeetCode 139题单词拆分，给定一个字符串s和一个单词字典wordDict，问s能否拆分成若干个字典里的单词。看起来和背包八竿子打不着，但你可以把s[0:i]能否拆分看作状态dp[i]，从位置j切一刀，如果dp[j]为真且s[j:i]在字典里，那dp[i]就为真。这本质上就是一个"每个单词可以用无限次"的完全背包求可行性问题。识别出这个对应关系，代码就很好写了。

6. 面试实战：拿到DP题的10分钟思考顺序

6.1 从记忆化搜索到DP：先写"暴力递归"再优化

面试过程中，很多人容易犯的毛病是拿到题目直接开始写状态转移方程，结果卡在定义上，越写越乱。我建议的流程是：前2-3分钟，先用"暴力递归"的思维把问题描述清楚。

比如01背包，暴力递归其实就是：

def dfs(i, rest_capacity): if i == n: return 0 # 不取第i个 res = dfs(i + 1, rest_capacity) # 取第i个（如果放得下） if rest_capacity >= w[i]: res = max(res, dfs(i + 1, rest_capacity - w[i]) + v[i]) return res

然后你观察这个递归函数，它有i和rest_capacity两个参数，这说明状态有两个维度。再用一个memo缓存计算结果，就变成了记忆化搜索。最后把递归改成循环填表，就得到了标准的DP解法。这个过程其实是在帮你理清"状态定义"和"转移逻辑"，比硬想方程要容易得多。

面试时我强烈建议你把这个推理路径说给面试官听：先写递归，再指出重复子问题，再加备忘录，再转递推。这个过程本身就展示了你的问题拆解能力，比直接甩dp[i][j]的公式令人信服得多。

6.2 边界条件检查的三个固定步骤

写完DP代码之后，不要急着说"做完了"。花10秒钟做三件事：

1. 检查数组长度：dp数组的长度是C+1还是C？有没有越界风险？
2. 检查初始化的语义：容量0的值是不是符合题目要求？不等价于0的情况（恰好装满、最小值）有没有特殊处理？
3. 检查遍历方向：内层循环是正序还是倒序？有没有可能覆盖还没用的旧值？

这三个步骤能挡住大部分运行时错误。我见过不少人栽在"数组初始化长度为C，但访问了dp[C]"这种低级错误上，面试时这种错误比算法不会更扣分，因为它说明你平时写代码不够细心。

6.3 空间优化的分寸感：不要一上来就写一维

我在面试中观察到一个很有意思的现象：候选人写01背包，一上来就写一维滚动数组的版本。代码确实没问题，但面试官追问"为什么倒序"时答不上来。这有点像背题。

我的建议是：如果面试官没有明确要求"优化空间"，你可以先写二维版本，讲清楚状态定义和转移逻辑，然后主动说"这个版本空间复杂度是O(n*C)，我可以优化成O(C)"。这样展示了两层能力：能写出正确解，也懂优化。反过来如果先写一维，被追问的时候紧张了容易露怯。

当然，如果题目本身的数据范围很大（比如C到10^6），二维数组根本开不下，就直接写一维，同时解释为什么可以滚动更新。

6.4 被追问"能再优化吗"时的三种思路

面试官经常在常规解法之后追问："还有其他优化吗？"这个时候可以从三个角度思考：

• 时间优化：能否减少状态维度？能否用单调队列优化多重背包？（这个比较深，一般不问）
• 空间优化：滚动数组、原地更新、用short类型存值等
• 剪枝优化：物品按性价比排序，用上界剪枝（这偏向搜索，DP题较少用）

其中空间优化是最高频的追问方向，其次是"如果物品数量很大但容量很小怎么办"这种问题——答案是把思路反过来，容量维度小就用容量做状态，物品多没关系。

7. 给刷题人的三个实测建议

文章最后这个部分，我想分享几个自己刷题和面试过程中的实际体会，不展开成章节了，就写最实用的三条。

第一条，背包问题的代码量其实很少，难的是识别和变通。我建议你把这篇文章里的三类背包模板（01、完全、多重）自己手写三遍，每次写都先口述一遍"为什么倒序/正序/二进制拆分"，再动笔。这样练下来的效果，比刷十道同类型题都好。

第二条，刷动态规划题的时候，建议专门用一个笔记记录每道题的"状态定义+转移方程+初始化"，不用写完整代码。面试前翻一翻笔记，比重新刷一遍题高效得多。动笔写的过程本身会逼迫你理清思路，这是纯看题解学不到的。

第三条，也是最重要的一条：面试时如果卡住了，不要慌，试着用暴力递归开始讲思路。面试官要看的不是你一次写对，而是你在不知道正解时的思考路径。动态规划这个题型尤其如此，很多候选人是"会做的都会，稍微变形就废"，本质原因就是没有从暴力递归的底层逻辑去理解状态定义。从递归到DP这个推导链，是你面试复习中最值得花时间的部分。

背包问题这块内容基本就是这些了，下一篇系列里我打算聊一聊区间DP和树形DP，这两个方向在面试中也经常出现，而且思维方式和背包类问题又不一样，到时候再把我踩过的坑和总结的技巧一并分享出来。