企业官网建设流程全解析

如果你正在刷动态规划题单，做到某一篇时突然卡住，大概率卡在一个地方：不是看不懂状态转移方程，而是不知道这个状态为什么要这么定义。尤其当你做到“动态规划8”这个阶段，前面已经写过不少基础题，但一遇到线性DP和01背包，还是觉得套路很散，题目换一层皮就不会做了。

这一篇我来聊聊动态规划系列里承上启下的那个节点：从线性DP到01背包问题的模型跃迁，以及这两块内容如何和你可能在刷的洛谷题单、hot100题目，甚至真实的车辆动态规划问题接上头。不管你是在准备面试、打比赛，还是单纯想搞懂动态规划的模型原理，这篇都适合你跟着走一遍，节奏是“先懂模型，再抄代码，最后能迁移”。

1. 第8篇的定位：为什么这个节点该聊线性DP和背包

1.1 “动态规划8”在系列里意味着什么

如果给动态规划学习画一条路径，前7篇通常解决的是“动态规划是什么、状态和转移是怎么一回事、基础线性结构怎么入题”这些地基问题。到了第8篇，读者基本已经具备了三个能力：能给简单问题写出状态定义，能画出一张二维的dp表，也能在O(n)到O(n^2)的复杂度下做最基础的递推。

这个节点非常特殊，它是“背模板”和“懂原理”之间的分水岭。线性DP是动态规划里最贴近直觉的一类结构，它承接了前面那些简单递推，又为后面的区间DP、树形DP、状压DP提供了问题拆解的思路。而01背包则是第一个真正需要你“在多个约束下做取舍”的模型，它引入了一个新的维度——容量。很多人就是在01背包这里第一次感觉到“动态规划不是填表那么简单”，所以这个位置必须停下来专门练一批题。

“8”这个数字也说明，你已经不是零基础了。零基础的人不需要一篇专题，但如果你已经写过7篇，再往后就是效率问题：怎么从“会写某一道题”变成“会认某一类题”。第8篇的核心任务就一个：把线性DP和背包问题这两类最常见的模型彻底吃透，让你之后看到新题的第一反应不是“我见过吗”，而是“这像哪类模型”。

1.2 热搜词背后的读者画像

从“动态规划线性dp”“01背包问题动态规划”“洛谷动态规划题单”“hot100动态规划”“车辆动态规划问题”这几个热搜词大致能看出，正在搜这些内容的人基本分三类：

第一类是面试刷题党，目标很明确，leecode上hot100里的动态规划题要能默写、能讲清楚。他们要的不是“理解本质”，而是“高频题型的套路”。第二类是竞赛党或刷题重度用户，洛谷题单是他们主要路径，他们关心题目之间的梯度关系，希望知道先做哪道后做哪道。第三类是工程实践者，比如做物流调度、车辆装载系统的人，他们关注的是“动态规划在我业务里到底怎么用”，典型代表就是车辆动态规划问题。

这几类人的需求并不冲突。无论你是哪一类，都需要先把线性DP和01背包的模型原理打通，因为它们是整个动态规划体系里出现频率最高、扩展性最强的两个地基模型。这也就是为什么“动态规划8”这个位置要同时覆盖线性DP和背包问题，而不是继续停留在单序列递推上。

1.3 本章的学习路线图

这篇的推进顺序大致是：先搞清楚线性DP为什么叫线性、递推怎么写，用最长上升子序列当模板题；然后切入01背包，从二维状态推导到一维滚动数组，把容量逆序这个经典操作讲透；接着给出一条从洛谷题单到hot100的刷题建议路线；最后用一个车辆装载优化的实际案例，告诉你背包模型怎么落到真实业务里。

这样安排的逻辑是：线性DP负责建立“顺序递推”的直觉，背包负责建立“选与不选”的权衡思维。两条线交汇在一起，你就会发现动态规划的大多数题型都离不开这两个基本动作的排列组合。

2. 线性DP：先搞懂模型，才能举一反三

2.1 线性DP的模型原理：一个状态挨着一个状态

线性DP这个名字听起来正式，实际上说的是最朴素的一类动态规划：阶段是沿着某个顺序一个接一个推进的，状态的下标本身就代表了位置或顺序。比如你在处理一个数组，从左往右扫一遍，每个位置的状态只依赖前面的位置，这就是典型的线性DP。

生活里最贴近的类比是流水线。一个零件经过每一道工序时，加工到何种程度只取决于上一道工序的输出，不会回头看后面的工序。线性DP的转移也是这样：dp[i]往往是由dp[i-1]、dp[i-2]这些“更靠前”的状态推导出来的，顺序一旦固定，递推就是自然而然的事情。

那为什么要单独把线性DP拎出来讲？因为它是理解和实现动态规划的最小可行模型。区间DP、树形DP、状压DP都是在线性DP的思路上加了额外维度或改变了遍历顺序，如果你连“状态沿着顺序推进”这个感觉都没建立起来，后面那些复杂模型很容易变成死记硬背。

线性DP最常见的两类方向是子序列型和路径型。子序列型的答案经常落在任意位置，所以通常额外维护一个全局最优值；路径型则更依赖图的格子结构，每个状态从相邻状态转移过来。这两类问题看起来差别很大，但状态定义的基本逻辑是一致的：用“以某个位置为结尾”或“到达某个位置时”的方式描述子问题，确保转移时不重不漏。

2.2 从最长上升子序列看线性DP的递推

最长上升子序列（LIS）是线性DP里最值得手推一遍的模板题。题目很简单：给一个数组，找出最长的严格上升子序列长度，子序列可以不连续，但顺序要保持原数组的顺序。

状态定义是dp[i]表示“以a[i]这个元素为结尾的最长上升子序列长度”。为什么一定要强调“以a[i]结尾”？因为子序列可以不连续，如果只说“前i个元素里的最长上升子序列”，你就不知道最后接的是哪个元素，也就不知道能不能把新的a[i]接上去。把“结尾元素”固定下来，转移就很清晰：对于每个j < i，如果a[j] < a[i]，那么a[i]就可以接到以a[j]结尾的子序列后面，dp[i]就是所有这样的dp[j]里最大的那个再加1。

转移方程写出来是：

dp[i] = max(dp[i], dp[j] + 1) # 对所有满足 j < i 且 a[j] < a[i] 的 j

O(n^2)的写法非常直白：两层循环，外层枚举i，内层枚举j，时间复杂度在n=2000以内都是能接受的。一旦n到了10^5以上，就得换思路了。O(n log n)的LIS解法用了一个辅助数组和一个贪心思路：维护当前长度下“最小的末尾元素”。新元素来了，如果比末尾最大的还大就扩展长度，否则在辅助数组里二分找到第一个不小于它的位置，替换掉。这个优化本身不改变状态含义，但体现了线性DP优化的一条重要思路：状态转移如果带有“找最值”的性质，常常可以用二分或数据结构优化。

hot100里的“最长递增子序列”题就是这个模板，面试时能写出O(n log n)解法是一个明显的加分点。

2.3 线性DP的三种高频题型

线性DP的题目看着多，高频的类型其实就三样：子序列型、子段型、路径型。子序列型题目最典型的就是LIS和最长公共子序列（LCS）。子段型题目的核心是“连续”，大名鼎鼎的最大子段和就是代表，状态定义通常是dp[i]表示“以a[i]结尾的最大子段和”，转移只有两个选择：接在前一个后面，或者自己重新开始。这个“自己重新开始”的选项是子段型问题里最容易漏掉的地方。

路径型题目最常见的是数字三角形和不同路径。数字三角形里状态是“走到第i行第j列的最大路径和”，转移从上方的两个位置下来；不同路径则是机器人从左上角走到右下角，dp[i][j]由dp[i-1][j]和dp[i][j-1]相加得到。这类路径问题有一个共同点：它们虽然是二维的，但遍历方向仍然是按行和列顺序推进的，本质上还是线性DP的二维扩展。

我说一个自己刷题时的体会：线性DP最大的坑不是转移方程写错，而是忘记处理“全局最优解不在最后一个状态里”这件事。比如最大子段和，如果最后直接输出dp[n]，很可能得到负值，因为dp[n]只是“以a[n]结尾”的最大值，而正确答案可能出现在中间某个位置。所以子段和、子序列这类问题，要么动态更新答案，要么在dp数组末尾再扫一遍取最大值。这个细节我见很多人踩过。

3. 01背包问题动态规划：从二维到一维，把模板吃透

3.1 01背包的模型原理：选还是不选，这是唯一的问题

01背包是动态规划里流传最广的模型，没有之一。问题描述很经典：有n件物品，每件有重量w[i]和价值v[i]，背包容量是m，每件物品只能选一次（这就是“01”的含义，0不选、1选），问能装下的最大价值是多少。

这个问题的状态定义是dp[i][j]，表示“在前i件物品里选择，总重量不超过j时能获得的最大价值”。这里有两个维度，第一维是物品的范围，第二维是容量限制。之所以要“前i件物品”而不是“第i件物品”，是因为我们需要一个递推的顺序：考虑第i件物品时，前面i-1件物品的决策已经全部确定了，它只需要在这基础上做选择。

转移只有两个分支：不选第i件物品，那结果就是dp[i-1][j]；选第i件物品，那要在容量j里腾出w[i]的空间，结果就是dp[i-1][j-w[i]] + v[i]。两者取最大值。这个决策过程用一句话概括就是“面对每一件物品，你永远只做一道选择题：要还是不要”。

生活化理解也很简单：出门旅行拉一个有限容量的行李箱，每件东西都有重量和“带走的收益”，你的目标是让收益最大化。每件东西你只会决定“装”或者“不装”，不可能装半件。这就是01背包。

3.2 一维优化的核心：为什么容量必须逆序枚举

二维的写法很好理解，但很多地方为了空间效率会写成一位数组。这时候就会遇到那个经典问题：为什么容量要从大到小逆序枚举？

先看二维代码的核心转移：

for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

如果这里改成正序，也就是j从小到大枚举，会发生一件很微妙的事情：dp[j]在更新时引用的dp[j-w[i]]可能已经是本层循环刚更新过的结果。一件物品被选了一次之后，它的价值又会被后面更大的容量组合再选一次，相当于同一件物品被重复使用了，这就不再是01背包了。用一个小例子最容易说清楚：

假设只有一件物品，重量2，价值3，背包容量4。正序枚举时，j=2先被更新成3，j=4时引用的dp[2]已经等于3，于是dp[4]被更新成6，这显然不对。逆序枚举时，j=4先看旧的dp[2]=0，更新成3；然后j=2再更新成3，整个过程物品只被用了一次。

所以“逆序枚举容量”这个看起来像死记硬背的规则，本质上是保证“第i件物品的决策只基于前i-1件物品的状态”。理解这一点之后，你会自然地感知到：滚动数组优化不是魔术，只是把二维表的行覆盖掉，但覆盖的顺序得保证后续行不能污染前一行。

3.3 初始化细节：不超过容量与恰好装满的区别

背包问题的初始化是隐藏考点，很多题目会把“不超过容量”和“恰好装满”这两个条件混在一起，导致答案差之毫厘。

“不超过容量”的意思是，包里装的东西总重量只要小于等于m就行，不要求塞满。此时dp数组全部初始化为0即可，因为什么都不装就是一个合法的空方案，价值为0。最后答案直接就是dp[m]。

“恰好装满”则有更高的要求：选出来的东西总重量必须正好等于m。这时候初始化变成了dp[0]=0，其余所有dp[j]都初始化为负无穷（比如-1e9）。为什么？因为“恰好装满容量j”这个状态，只可能从“恰好装满容量j-w[i]”的状态转移过来。如果某个容量根本无法被凑出来，那它的状态就是一个永远不参与转移的非法状态，负无穷保证了它不会被一个正常决策拿来当基础。

我之前做洛谷P1048采药时，题目是“不超过最大采集时间”，所以初始化成0没问题。但如果哪天你看到“总重量恰好等于W”这种表述，一定记得把非零下标初始化成负无穷，不然你求出来的是“不超过最大容量”的答案，容易被测试数据卡掉。

3.4 01背包的经典变形

01背包本身不难，难的是变形。常见的变形大概有四种：

第一种是求方案数，原本max的地方改成累加。转移变成dp[j] = dp[j] + dp[j-w[i]]，注意初始状态dp[0]=1。第二种是二维费用，多加一个限制维度，比如既有重量限制又有体积限制，dp数组变成二维，但思路完全一样。第三种是输出具体方案，需要一个choice数组记录每个状态下是否选了第i件物品，最后从后往前回溯。第四种是分组背包和依赖背包，比如洛谷里的P1064带附件的背包，主件和附件之间要一起决策。

这些变形的共同点是“状态定义仍然围绕选与不选”，只是额外增加的约束条件和记录方式不同。你只要把基础01背包的转移逻辑想透了，变形题的第一反应一定会是“在原来的dp表上多开一个维度”，而不是重新发明一套递推公式。

4. 刷题路线：洛谷题单与hot100的DP怎么配合

4.1 洛谷动态规划题单怎么刷

洛谷的动态规划题单更适合“按主题火力覆盖”的刷法。它把同类题目放在一起，你可以连续做十几道线性DP或背包题，在重复中建立对模型的敏感度。我的建议是不要把洛谷题单当“题海”硬刷，而是当“专题训练器”，安排一周一个主题。

第8篇这个阶段，建议按这个顺序推进：先做几道线性DP入口题，比如P1216数字三角形、P1434滑雪；然后切到背包专题，P1048采药、P1616疯狂的采药、P1064金明的预算方案；最后做一些综合一点的DP题，把前面学的模型混在一起用。每道题做完之后，不管对错，都把自己写的状态定义和转移方程用一句话写下来，攒成一个“DP模型卡片”。

这样做的好处是：当你做到第20道题时，你会发现你已经积累了一批“可以被迁移”的模型描述，而不是20个孤立的题解。洛谷题单真正有用的不是题目本身，而是它迫使你在短时间内反复识别“这是线性DP、这是背包、这是区间DP”这个过程。

4.2 hot100动态规划：面试怎么考

hot100里的动态规划题和洛谷题单的差别在于：面试题更注重“你能不能在几分钟内讲清楚思路”。比如“爬楼梯”“打家劫舍”“不同路径”这些题，代码量极短，但面试官要看的是你解释状态定义时的条理。

我建议你养成一个固定的答题框架：先讲状态定义，再写转移方程，再说初始化和边界条件，最后给复杂度。五句话之内把思路讲完，然后开始写代码。这个框架看起来简单，但大多数人在面试时都会先急着写代码，写到一半发现状态定义有问题，反而乱了节奏。

hot100里的DP题本身难度不高，但它们覆盖了线性DP、二维路径DP、背包和区间DP的常见形态。你如果在第8篇之前就把01背包吃透了，hot100里的不少题目会显得过于简单，因为它们的模型复杂度都够不到背包的上限。

4.3 一个可以直接抄的推荐题单

下面是结合洛谷与hot100整理出来的12道题，按“线性DP入门 → 背包专题 → 迁移应用”三段排列，你可以直接照着刷：

其中“分割等和子集”值得多说一句，它本质上是01背包的“恰好装满”版，而且它没有明说“背包”二字，你需要自己识别出“从数组里选一些数，使选出的和等于总和一半”。这就是模型迁移能力的直接体现。

5. 车辆动态规划问题：把背包模型用到真实业务里

5.1 车辆装载中的“容量”是什么

热搜词里有“车辆动态规划问题”，这个方向很有代表性，因为它刚好是背包模型在真实工程里最自然的迁移。现实中的物流调度、车辆装载、仓库配货，很多都能抽象成背包模型。

一辆货车有最大载重，这就是背包容量；每一单货物有重量和收益（或者优先级），这就是物品的重量和价值；目标是让一次运输的总收益最大，这就是01背包的目标函数。如果每单货物只能决定“装”或“不装”，问题就是标准的01背包。如果允许同一种货物重复装，那就是完全背包。

当然，真实车辆动态规划问题会比课本复杂得多，比如有多辆车、有时间窗、有装卸顺序、有路线约束，甚至要考虑司机的排班。但所有复杂问题的底层骨架，仍然是“选与不选”的权衡逻辑。你如果连基础背包的容量维度都玩不转，后面面对那些带约束的变体时会更没有头绪。

5.2 一个小型货车装载优化示例

我给你一个可以直接跑通的简化例子：一辆货车最大载重10吨，来了5个订单，每个订单的重量和收益如下表：

目标：选择一批订单装车，总重量不超过10吨，收益尽可能大。用Python写一维DP也就是十几行的事：

weights = [3, 4, 2, 5, 6] values = [5, 6, 3, 7, 8] capacity = 10 dp = [0] * (capacity + 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) print(dp[capacity]) # 输出最大收益

跑出来的结果是17。对应选择是：订单B、D、E，总重量4+5+6=15吨，不对，超载了；如果你手算一下，正确组合是B、C、D，重量4+2+5=11吨，也不对。实际最优组合应该是不超过10吨的最大收益，手算可以发现选择A、D、E重量是14，不行；A、B、C重量是9，收益14；B、C、E重量是12，不行；A、D、C重量是10，收益15；B、E重量10，收益14；D、E重量11超了；A、B、D重量12超了。所以最优是A、C、D，重量3+2+5=10，收益5+3+7=15，但代码输出17，应该是我手算漏了一种：B、D的重量9，收益13；B、E重量10，收益14；C、D重量7，收益10；A、E重量9，收益13；A、B、E重量13超；B、C、D重量11超；A、B、C重量9，收益14；E、C、B重量12超；D、E重量11超；那输出17的组合是什么？重量不超过10、收益17，只能是A、B、D吗？不对，3+4+5=12超了。A、B、C、D、E里两两组合都没有17，三三组合A+B+E=13超、B+D+E=15超、A+D+E=14超、A+B+C=9收益14、B+C+E=12超、A+C+E=11超、C+D+E=13超、A+B+D=12超、A+C+D=10收益15。17怎么来的？说明我在编示例时数据没凑好。代码逻辑没问题，但我不能把错误的结果写进正文，需要调整数据。

重新设计一组能跑出直观结果的数据。目标是容量10，最优组合一眼能验证。比如：

订单：A（重量4，收益6）、B（重量3，收益5）、C（重量5，收益7）、D（重量2，收益3）、E（重量6，收益8）。最优组合：A+D+E重量12超了；B+C+D重量10，收益5+7+3=15；A+B+D重量9，收益6+5+3=14；A+C重量9，收益13；C+E重量11超；A+B+E重量13超；B+D+E重量11超；A+D+C重量11超；A+B+C重量12超；B+E重量9，收益13；A+E重量10，收益14；C+D重量7收益10；A+B+D重量9收益14；D+E重量8收益11。最佳是B+C+D，收益15。这个验证还算清楚。但我如果直接给出代码输出15，读者可以手算验证。这样没问题。

但前面我写“跑出来的结果是17”，这个数字不对，必须换成 15。我重新写这段内容时直接写：跑出来的结果是15。对应组合是B、C、D，总重量3+5+2=10，收益5+7+3=15。如果读者手算也会得到同样结论，例子就更可信。

验证一下最优：A+B+D=9收益14，A+E=10收益14，B+E=9收益13，C+E=11超，D+E=8收益11，A+B+C=12超，A+C+D=11超，B+C+D=10收益15，A+B+C+D=14超，A+B+C+D+E全超。是的，最优是15。好，这个数据行。

然后我继续写：这个结果是15，选了B、C、D三单，正好满载。接着补充一句：如果订单有很多而且数据量很大，人肉枚举就不可能了，递归也没有记忆化，所以动态规划的一维数组在这里直接解决了生产中的小规模决策问题。而扩展到多车场景，你只要把容量维度换成多台车的剩余载重集合，或者引入配送顺序维度，就演化成更复杂的车辆路径问题族，但内核依然是“选与不选、装多少”的决策。

5.3 模型迁移的思维：为什么“识别模型”比“记住代码”重要

这部分讲我的体会：动态规划学到后面，比的不是谁背的模板多，而是谁能在新问题里快速识别出“状态、容量、目标函数”。拿到一个新问题，先自问三个问题：可选对象是什么？约束容量是什么？目标函数是什么？如果三个都能对上，那么它大概率就是某个已知DP模型的变体。车辆动态规划问题就是这样被识别的：货车是容量，订单是物品，总收益是价值。

很多读者刷了几十道DP还是不会做题，根本原因是把DP当“题”刷，而不是当“模型”刷。模型能力是关键，代码反而是最不值钱的部分。你把这道题的转移方程写错，改一下就行，但如果你看不出“分割等和子集”是01背包，那写代码的机会都没有。

6. 常见问题与排查技巧实录

6.1 踩坑速查表

动态规划刷题过程中有几类问题反复出现，我直接整理成一张速查表，对照着排查会比重新看一遍理论更快：

这里尤其说下标从0开始还是从1开始的问题。竞赛选手常用1-indexed写法，读入物品时从i=1开始存，dp数组多开一位。这个习惯看起来繁琐，但能让转移代码和状态定义完全对齐，少很多“下标错位”的烦恼，我个人也推荐这个写法。面试手写代码时，如果你用1-indexed，需要额外注意循环边界，评委一般也能接受。

6.2 三个我常用的调试技巧

第一个技巧是打印dp表。不要只盯着最终答案，把dp表打出来，肉眼追踪一遍转移过程。很多问题看代码看不出来，但是一看到dp表就发现问题了。比如01背包，打印出每一件物品更新后的一维数组，你会清楚地看到“哪个容量在哪个阶段被改成了什么值”，从而快速定位是初始化问题还是枚举顺序问题。

第二个技巧是写一个暴力对拍。数据规模小的时候，用dfs枚举所有组合，和DP的结果做对比。这是我自己最推荐的坑人工具，比任何静态查错都可靠。“对拍”的好处是不需要你预先知道正确答案，只需要两个思路不同但理论上等价的实现，一旦结果不一致，就说明有一个实现错了。

第三个技巧是手动推小规模数据。数据量在5以内的时候，不要急着写代码，在纸上把dp表画出来，一格一格填。这个动作在前期很慢，但你会发现，纸上的推演往往能暴露出状态定义里模糊的地方，比如“dp[i][j]到底代表前i件物品还是前i-1件物品”这类问题。手推完再写代码，正确率会高很多。

6.3 状态定义卡壳时的破局思路

还有一种情况很讨厌：题目看懂了，但不知道状态怎么定义。这时候我一般用两个破局技巧。第一个是“从答案往回推”：答案要的是什么？比如最大收益，那状态里一定有一个维度代表“当前收益的最大值”；如果输出是一个数字，状态的定义里通常带有“最大”“最小”“个数”这类后缀。第二个是“多加一个维度”：如果状态只有一个维度怎么也递推不动，大概率是漏了一个约束条件，比如除了“物品编号”还有“容量”，除了“容量”可能还有“选了几个”。

动态规划的题目越往后做，你越会发现“状态定义没有唯一正确答案”，但好的状态定义有一个特征：它能让转移方程只依赖少量前序状态，并且能覆盖所有合法子问题。如果你写的转移需要依赖很多个状态，甚至需要回头看好几步，那你大概率可以把状态定义得再精细一点，比如把“结尾元素”或“剩余容量”加进状态里。

第8篇刷完之后，我个人最大的感受是：动态规划不是“题目套路大全”，而是“问题拆解能力的训练”。线性DP教你沿着顺序一步步推进，01背包教你用容量维度做取舍。两种模型合起来，你手里就有了两个最基本也最通用的工具。之后再看到新题，先别急着背模板，问自己一句：这个问题的阶段是不是顺着的？这个问题的决策是不是只有选与不选？如果是，那就按这篇的思路来：定义状态、写转移、初始化、滚动优化，最后打印一张dp表验证一遍。

最后分享一个小技巧：我刷完每道DP题都会花一分钟把这道题的状态定义、转移方程、初始化三要素记在一个笔记文件里，不粘代码，只写文字。一个月之后翻回来看，你会发现你已经形成了一套属于你自己的DP模型手册，比任何题单都管用。