做动态规划做到第八期回头看看踩过的坑、总结过的套路确实值得单独写一篇复盘。这系列前七篇我分别讲了状态设计、转移方程、记忆化搜索、数位DP、树形DP、优化技巧和经典模型这次“动态规划8”就换个角度不堆新模型而是把所有核心模型原理串起来重点拆线性DP和背包问题这两条主线顺便聊聊车辆动态规划这类实际问题怎么用DP思想就当是阶段性总结加实战手册。如果你是刚跟着题单刷到这里的同学或者刷了hot100但总在背包问题上卡壳这篇应该能帮上忙。很多人刷动态规划总觉得“一看就会一写就废”问题往往不在代码而在建模那一步。本篇就从模型原理切入把状态、转移、边界、优化一整个链路拉开配合洛谷题单和常见工程案例尽量让你看完能直接照着写。1. 动态规划的核心模型与解题套路1.1 动态规划到底在“规划”什么动态规划的本质是对“状态”做决策。我们用一组变量描述当前情况的所有关键信息这个描述就是状态从当前情况做出下一步选择后到达新情况这个过程就是转移。整个问题因此变成一个多阶段决策的最优化问题。你吃东西点外卖就是个天然例子当前手里有预算和饥饿值是状态每一道菜的价钱和热量是决策吃完一份后预算减少、饥饿值下降是转移目标是花最少的钱获得最大满足感就是目标函数。动态规划要做的就是枚举所有可能的“吃法组合”但用状态复用避免重复计算。这引出一个关键认知只要状态定义得足够完整能够覆盖所有影响未来决策的信息那么把问题拆成子问题后最优解一定可以通过最优子结构拼出来。这也是动态规划有效的前提无后效性和最优子结构两个概念说的其实是一件事当前决策只影响未来不影响过去的最优结论。1.2 从状态定义到转移方程先解决“为什么”初学时我总急着写转移方程后来发现这是最效率最低的做法。正确顺序是先回答四个问题问题里哪些量是可变的且会随决策变化这些量里哪些会影响后续决策必须放进状态当前这个状态是从哪些前驱状态转移来的转移时取了max还是min边界值是什么比如线性DP里的经典问题“最长上升子序列”核心变量是“当前位置”和“末尾元素大小”。我们定义dp[i]表示以第i个元素结尾的最长上升子序列长度遍历所有j i当nums[j] nums[i]时尝试更新dp[i] max(dp[i], dp[j] 1)。这里为什么把“以i结尾”而不是“前i个”作为状态因为“以i结尾”保留了末尾元素这个关键信息后续能否拼接下一个更大元素完全取决于末尾值如果只定义“前i个的最长长度”就丢失了末尾大小没法进行后续决策。这就是状态设计的核心逻辑。再强调一点转移方程不是“猜”出来的而是“从前驱状态向后继状态推”推出来的。画一张小图把所有前驱状态列出来方程自然就写出来了。1.3 三类高频DP模型对比把洛谷题单和LeetCode hot100翻一遍会发现高频模型其实就几类。这里重点梳理三类线性DP状态维度是“位置”通常是dp[i]表示处理完前i个元素或到达第i个位置的最优值。代表问题最大子段和、最长上升子序列、数字三角形、爬楼梯。区间DP状态从“位置”变成“区间左右端点”dp[l][r]表示闭区间[l, r]上的最优解转移通常枚举分割点k。代表问题石子合并、回文串分割、矩阵链乘。背包DP状态是“决策约束的组合”dp[i][j]表示前i个物品在容量为j的背包中获得的最大价值。它本质是资源分配问题所有“有容量限制、有选择成本”的题几乎都能套背包。这三类不是互斥的线性DP中最长公共子序列也相当于双序列线性DP背包也是线性枚举的。把它们分开是为了快速定位模型实际做题时也可以综合使用。建议每类各找十道题先把同一模型的题刷出感觉再混合训练。2. 线性DP实战拆解从数字三角形到双序列2.1 数字三角形线性DP的“第一课”洛谷P1216数字三角形是一个极好的入门题。题目给出一个三角形从顶部出发每次可以向下或向右下走要求路径上数字之和最大。很多人一上来就写搜索其实这是典型的线性DP。定义dp[i][j]表示从顶部走到第i行第j列位置时所获得的最大和。转移方程dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]从左上过来即上一行第j-1列从正上方过来即上一行第j列边界是dp[1][1] a[1][1]其他无效位置用极小值初始化。这个转移为什么可靠因为走到当前位置只有两个方向前面每一步都已经依赖子结构被预处理出来了这就是线性DP“顺着位置从左到右、从上到下”推进的典型形态。实现时候有两点容易翻车一是二维数组越界建议把行、列坐标从1开始读入把边界多留一圈初始化成负无穷二是如果从上往下填表记得只枚举当前行有效列范围别把三角形外部的空格也当成0参与运算。2.2 最大子段和一维线性DP的状态压缩另一个很能说明问题的线性DP是最大子段和。给定一个数组求连续子数组的最大和。这道题最常见的O(n)写法是pre max(pre nums[i], nums[i]) res max(res, pre)这里的pre说白了就是“以当前元素结尾的最大子段和”。很多人背下这段代码却不理解为什么pre要么累加要么重置。其实dp[i]表示以第i个元素结尾的最大子段和转移只有两种选择把当前元素接到前一个子段后面dp[i] dp[i-1] nums[i]单独成段dp[i] nums[i]取较大的那个就是pre max(pre nums[i], nums[i])。因为dp[i]只依赖dp[i-1]所以可以用一个变量滚动更新这就是空间优化的雏形。这个例子还能很好解释“状态复用”计算dp[100]时dp[1]到dp[99]的最优结论已经在滚动中被重复利用不需要重新计算。2.3 双序列线性DP最长公共子序列的转移矩阵最长公共子序列LCS是双序列线性DP的代表也是hot100和洛谷题单的常客。定义dp[i][j]表示字符串A的前i个字符和B的前j个字符的最长公共子序列长度。转移分情况如果A[i] B[j]那么dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])很多人不理解为什么不等时要取两个方向的最大值。原因是如果当前两个字符不相等那么现在的最长公共子序列要么来自“A去掉当前字符后和B的前j个”的结果要么来自“A的前i个和B去掉当前字符后”的结果这两个候选都不一定是在同一个端点结束所以要取最大值。这个问题的转移构成了一个二维表格每一个格子只依赖左、上、左上三个方向。算完整个表后dp[n][m]就是答案。实际写代码时如果要用滚动数组要注意更新顺序因为dp[i][j]依赖dp[i-1][j-1]一旦覆盖当前行就可能丢失左上的旧值。通常用两个临时变量保存左上方和左边的旧值或者干脆不加优化先写完整二维ac后再考虑空间优化。这类双序列问题的核心经验是把两个序列的长度作为两个维度写进状态状态转移就是“当前字符匹配/不匹配”的分支讨论。凡是“两个字符串/数组之间找关系”的题八成都可以尝试双序列DP。3. 背包问题模型01背包、完全背包与滚动数组3.1 01背包的状态设计与转移推导01背包是动态规划里最经典的模型之一。每件物品只有取或不取两种选择目标是背包容量有限时获得最大总价值。洛谷题单里的采药、开心的金明hot100里的分割等和子集底层都是01背包。先说标准定义有n个物品第i个物品重量为w[i]价值为v[i]背包总容量为C。定义dp[i][j]表示考虑前i个物品当前背包容量为j时能获得的最大价值。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 当j w[i] dp[i][j] dp[i-1][j] 当j w[i]第一个max里dp[i-1][j]是不取第i个物品dp[i-1][j-w[i]] v[i]是取第i个物品先腾出w[i]的容量再放进去。这里为什么要用i-1状态因为01背包要求每个物品只能选一次不能在同一轮里复用同一个物品所以必须参考上一轮的处理结果。图示化思考整个dp表是一个n×C的矩阵i方向是物品顺序j方向是容量。每个格子的值只由它上面一行同一列和左上方某个格子的值决定。方向明确代码就好写了。3.2 滚动数组优化与遍历顺序的“禁忌”很多新手优化背包空间把二维dp压成一维dp[j]后发现结果莫名其妙变了。原因就出在遍历顺序上。一维优化的标准写法for i in 1..n: for j in C..w[i]: # 注意从大到小 dp[j] max(dp[j], dp[j-w[i]] v[i])为什么j要从大到小遍历因为一维dp[j]在更新时dp[j-w[i]]必须仍然是“上一轮i-1”的结果而不能是当前轮已经更新过的结果。如果j从小到大遍历dp[j-w[i]]可能刚被本轮更新过相当于同一个物品被选了多次这就不再是01背包变成完全背包了。这是动态规划题目里最经典的“顺序陷阱”没有之一。我踩过这个坑两次之后总结了一个记忆方法01背包是“从大到小偷着更新”完全背包是“从小到大正大光明更新”。把这个顺口溜记下来背包题基本不会因为遍历方向再出问题。3.3 完全背包与多重背包的差异完全背包表示每个物品可以无限取用转移方程看似一样只是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])关键区别在于取第i个物品后剩余部分依然可以考虑再次取第i个物品所以依赖的是当前行dp[i][j-w[i]]而不是上一行dp[i-1][...]。用一维数组写的时候j从小到大遍历正好能利用本行已经更新的值实现“无限复用”。多重背包则介于二者之间每个物品有数量限制count[i]。如果count很大可以二进制拆分把多个相同物品拆成1、2、4...份转成01背包处理。这样做的正确性在于任意数量都可以由这些二进制分组组合出来而拆出的每一组又只能取一次恰好符合01背包的约束。做题时首先要判断每个物品可用的次数一次01、无限次完全包、有限次多重宝。这个判断错了遍历顺序也就跟着错最后的dp表全乱。建议每次写背包题前在注释里写清“类型遍历方向”习惯养成就很少翻车。4. 从算法题到工程车辆动态规划问题中的DP思想4.1 车辆调度为什么能抽象成DP算法题里的DP刷多了会发现真实工程中的很多问题也带着DP的影子车辆动态规划就是典型例子。这里说的“车辆动态规划问题”不是某一个具体题目而是一大类资源调度优化问题比如配送车辆路径选择、出租车调度、共享汽车投放本质都是在容量、时间、里程等约束下对“车辆”这个资源做最优分配。我们用一个简化场景说明一辆车从起点出发要依次服务若干客户点每个点有最早服务时间和最晚服务时间车辆有载重上限问最多能服务多少个点或者总行驶距离最短。这很像时间窗约束下的路径问题完整解决需要组合优化算法但可以考虑用DP处理其中一部分。比如假设路线顺序已经确定那么“当前到达某个点时剩余多少时间、还能接多少货”就可以作为状态做容量限制下的收益最大化这就是一个带时间约束的背包。更常见的是“车辆数目运输任务分配”问题多辆车分别装载不同货物每辆车容量有限希望总成本最小这种分配问题可以直接建模成多维背包每件货物选或不选每辆车对应一个容量维度。4.2 用多维背包模拟车辆装载问题假设有三辆车容量分别是C1、C2、C3有n件货物每件重量w[i]、运送价值v[i]每件货物必须由某一辆车运输且每辆车的总重量不能超载目标是最大化总运送价值。这就是一个三维背包dp[a][b][c]表示三辆车分别已用容量a、b、c时的最大价值。每件货物依次决策分别尝试放入第一辆、第二辆、第三辆或者不放。转移dp[a][b][c] max(dp[a][b][c], dp[a-w[i]][b][c] v[i] if aw[i], dp[a][b-w[i]][c] v[i] if bw[i], dp[a][b][c-w[i]] v[i] if cw[i])用滚动数组写的时候三个维度都要从大到小遍历原理和01背包一维优化完全一样保证每件货物只被考虑一次。实际工程里维度可能更多比如还要加时间窗、冷热链、司机休息时间维度一多DP表会指数膨胀这时就需要换成启发式算法或列生成。不过这不代表DP思想没有用恰恰相反很多启发式算法在局部优化阶段还是会用DP做“容量分配”的子模块所以算法题里练好的背包模型在工程项目里是能直接迁移的基础能力。4.3 DP落地的工程注意事项真实车辆动态规划问题和刷题有几个明显差别值得特别提醒维度爆炸动态规划表的大小随着状态维度指数增长三辆车可能还勉强十辆车就没法直接开三维数组了。工程上要么压缩状态要么放弃精确DP用近似方法。边界条件复杂车辆路径问题里“容量”“时间窗”“服务时间”相互耦合状态必须定义得更细否则漏掉约束会导致结果不可用。性能要求线上系统往往要求毫秒级响应DP如果规模太大需要配合剪枝、预处理和空间压缩。我见过一个团队直接把算法竞赛的二维背包代码搬上生产环境结果输入一变成百辆车就内存爆掉。后来他们用贪心先排一个初始解再用DP只优化几个关键环节才把效果和性能都平衡下来。这个经验很重要工程里DP是解决问题的工具之一不是非要满状态求解才算用DP。5. hot100视角动态规划高频题与常见错误自查5.1 高频DP题型的模型映射把LeetCode hot100里和DP相关的题目过一遍会发现它们绝大多数能归入前文提到的模型。这里做一张映射表供自查题目类型核心模型状态定义爬楼梯线性递推dp[i]表示到达第i阶的方法数最大子序和线性DPdp[i]表示以i结尾的最大子段和打家劫舍线性DPdp[i]表示前i间房能偷到的最大值最长递增子序列线性DPdp[i]表示以i结尾的LIS长度分割等和子集01背包dp[j]表示是否能用元素凑出和j零钱兑换完全背包dp[j]表示凑出金额j的最少硬币数编辑距离双序列DPdp[i][j]表示A前i个字符到B前j个字符的编辑距离看到题目先对号入座能少走很多弯路。很多人喜欢直接凭感觉写写到一半发现状态不全推倒重来其实花一分钟先想清楚模型后面反而快很多。5.2 初始化与边界最容易翻车的地方刷了这么多题我总结的DP错误里初始化错误占比远超转移方程错误。常见问题包括求最大值却把dp数组初始化为0导致负权路径被错误忽略。正确做法是针对求解目标求最大值时非法状态用负无穷如-1e9求最小值时用正无穷如1e9。边界漏算。比如dp[0]到底代表“空集合”还是“第一个元素”这个问题必须想清楚。像分割等和子集dp[0]要置为true表示空集能凑出0其他置为false。字符串数组从0还是从1开始。如果从0读入转移时dp[i-1]可能出现负数下标建议统一把数据下标后退一位dp数组多开一位。我自己每次写完DP都会做三个边界测试空输入、最小规模、最大规模。比如n1时答案是什么C0或者容量为0时dp表变化是否符合预期这些测试虽然简单却经常能揪出初始化问题。5.3 调试DP的实用手段打表与对比调试DP最有效的办法不是单步跟踪而是把dp表完整打出来逐行检查是否合理。我通常会在关键转移后加一段临时输出for i in range(1, n1): for j in range(1, C1): print(dp[i][j], end ) print()然后拿一个非常小的样例手工推算一遍DP表把推出来的表格和程序输出对比。只要某个格子对不上就顺着它背后的转移链往回找问题基本都能定位。这条方法虽然土但比任何调试器都好用。另一个技巧是写一个暴力解法的对拍器DP写完后用随机数据让两组代码同时跑结果不一致就不断缩小数据规模。我在刷hot100时经常这么干特别是转移方向容易混的背包题对拍能节省大量手动验算时间。5.4 动态规划学习路径的建议八期内容走到这里如果还想继续往前推进我给一条实操路径。第一把线性DP和背包彻底吃透。这两块像动态规划的地基把状态设计、滚动数组、初始化这些基本功练熟其他模型都是延展。第二顺着洛谷题单刷题每一道题都要能说出三个东西状态定义、转移方程、边界条件。不能说出这三样说明这道题还没真正掌握哪怕AC了也是背模板。第三利用hot100查漏补缺。hot100里的DP题相比洛谷更偏工程思维题目描述更接近真实问题场景能把模型从竞赛转换为落地很有价值。第四学有余力再拓展区间DP、状态压缩DP、树形DP。前七期内容已经把树形DP和数位DP铺垫过了这一期主要是把公共主线串一遍后面可以针对薄弱模型再各写专题。我自己到现在写DP依然会在草稿纸上先写清“dp[i][j]代表什么”再动代码。这一步看起来多花三分钟但能防止后面半小时的无效调试。状态定义清晰转移方程基本是水到渠成的事。最后分享一个小经验遇到一个新问题先别急着套模型试试把题目改成“有一组选项、每个选项消耗资源且带来收益、总资源有限”的描述如果改得顺多半就是背包改成“从前往后依次处理每个位置当前状态只依赖前几个位置”多半就是线性DP。这套判断思路在车辆动态规划和hot100里都帮我快速定过方向。希望这一篇也能让你在DP这条路上少踩几个坑多几分确定性。
动态规划核心模型全解析：线性DP、背包问题与实战应用
做动态规划做到第八期回头看看踩过的坑、总结过的套路确实值得单独写一篇复盘。这系列前七篇我分别讲了状态设计、转移方程、记忆化搜索、数位DP、树形DP、优化技巧和经典模型这次“动态规划8”就换个角度不堆新模型而是把所有核心模型原理串起来重点拆线性DP和背包问题这两条主线顺便聊聊车辆动态规划这类实际问题怎么用DP思想就当是阶段性总结加实战手册。如果你是刚跟着题单刷到这里的同学或者刷了hot100但总在背包问题上卡壳这篇应该能帮上忙。很多人刷动态规划总觉得“一看就会一写就废”问题往往不在代码而在建模那一步。本篇就从模型原理切入把状态、转移、边界、优化一整个链路拉开配合洛谷题单和常见工程案例尽量让你看完能直接照着写。1. 动态规划的核心模型与解题套路1.1 动态规划到底在“规划”什么动态规划的本质是对“状态”做决策。我们用一组变量描述当前情况的所有关键信息这个描述就是状态从当前情况做出下一步选择后到达新情况这个过程就是转移。整个问题因此变成一个多阶段决策的最优化问题。你吃东西点外卖就是个天然例子当前手里有预算和饥饿值是状态每一道菜的价钱和热量是决策吃完一份后预算减少、饥饿值下降是转移目标是花最少的钱获得最大满足感就是目标函数。动态规划要做的就是枚举所有可能的“吃法组合”但用状态复用避免重复计算。这引出一个关键认知只要状态定义得足够完整能够覆盖所有影响未来决策的信息那么把问题拆成子问题后最优解一定可以通过最优子结构拼出来。这也是动态规划有效的前提无后效性和最优子结构两个概念说的其实是一件事当前决策只影响未来不影响过去的最优结论。1.2 从状态定义到转移方程先解决“为什么”初学时我总急着写转移方程后来发现这是最效率最低的做法。正确顺序是先回答四个问题问题里哪些量是可变的且会随决策变化这些量里哪些会影响后续决策必须放进状态当前这个状态是从哪些前驱状态转移来的转移时取了max还是min边界值是什么比如线性DP里的经典问题“最长上升子序列”核心变量是“当前位置”和“末尾元素大小”。我们定义dp[i]表示以第i个元素结尾的最长上升子序列长度遍历所有j i当nums[j] nums[i]时尝试更新dp[i] max(dp[i], dp[j] 1)。这里为什么把“以i结尾”而不是“前i个”作为状态因为“以i结尾”保留了末尾元素这个关键信息后续能否拼接下一个更大元素完全取决于末尾值如果只定义“前i个的最长长度”就丢失了末尾大小没法进行后续决策。这就是状态设计的核心逻辑。再强调一点转移方程不是“猜”出来的而是“从前驱状态向后继状态推”推出来的。画一张小图把所有前驱状态列出来方程自然就写出来了。1.3 三类高频DP模型对比把洛谷题单和LeetCode hot100翻一遍会发现高频模型其实就几类。这里重点梳理三类线性DP状态维度是“位置”通常是dp[i]表示处理完前i个元素或到达第i个位置的最优值。代表问题最大子段和、最长上升子序列、数字三角形、爬楼梯。区间DP状态从“位置”变成“区间左右端点”dp[l][r]表示闭区间[l, r]上的最优解转移通常枚举分割点k。代表问题石子合并、回文串分割、矩阵链乘。背包DP状态是“决策约束的组合”dp[i][j]表示前i个物品在容量为j的背包中获得的最大价值。它本质是资源分配问题所有“有容量限制、有选择成本”的题几乎都能套背包。这三类不是互斥的线性DP中最长公共子序列也相当于双序列线性DP背包也是线性枚举的。把它们分开是为了快速定位模型实际做题时也可以综合使用。建议每类各找十道题先把同一模型的题刷出感觉再混合训练。2. 线性DP实战拆解从数字三角形到双序列2.1 数字三角形线性DP的“第一课”洛谷P1216数字三角形是一个极好的入门题。题目给出一个三角形从顶部出发每次可以向下或向右下走要求路径上数字之和最大。很多人一上来就写搜索其实这是典型的线性DP。定义dp[i][j]表示从顶部走到第i行第j列位置时所获得的最大和。转移方程dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]从左上过来即上一行第j-1列从正上方过来即上一行第j列边界是dp[1][1] a[1][1]其他无效位置用极小值初始化。这个转移为什么可靠因为走到当前位置只有两个方向前面每一步都已经依赖子结构被预处理出来了这就是线性DP“顺着位置从左到右、从上到下”推进的典型形态。实现时候有两点容易翻车一是二维数组越界建议把行、列坐标从1开始读入把边界多留一圈初始化成负无穷二是如果从上往下填表记得只枚举当前行有效列范围别把三角形外部的空格也当成0参与运算。2.2 最大子段和一维线性DP的状态压缩另一个很能说明问题的线性DP是最大子段和。给定一个数组求连续子数组的最大和。这道题最常见的O(n)写法是pre max(pre nums[i], nums[i]) res max(res, pre)这里的pre说白了就是“以当前元素结尾的最大子段和”。很多人背下这段代码却不理解为什么pre要么累加要么重置。其实dp[i]表示以第i个元素结尾的最大子段和转移只有两种选择把当前元素接到前一个子段后面dp[i] dp[i-1] nums[i]单独成段dp[i] nums[i]取较大的那个就是pre max(pre nums[i], nums[i])。因为dp[i]只依赖dp[i-1]所以可以用一个变量滚动更新这就是空间优化的雏形。这个例子还能很好解释“状态复用”计算dp[100]时dp[1]到dp[99]的最优结论已经在滚动中被重复利用不需要重新计算。2.3 双序列线性DP最长公共子序列的转移矩阵最长公共子序列LCS是双序列线性DP的代表也是hot100和洛谷题单的常客。定义dp[i][j]表示字符串A的前i个字符和B的前j个字符的最长公共子序列长度。转移分情况如果A[i] B[j]那么dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])很多人不理解为什么不等时要取两个方向的最大值。原因是如果当前两个字符不相等那么现在的最长公共子序列要么来自“A去掉当前字符后和B的前j个”的结果要么来自“A的前i个和B去掉当前字符后”的结果这两个候选都不一定是在同一个端点结束所以要取最大值。这个问题的转移构成了一个二维表格每一个格子只依赖左、上、左上三个方向。算完整个表后dp[n][m]就是答案。实际写代码时如果要用滚动数组要注意更新顺序因为dp[i][j]依赖dp[i-1][j-1]一旦覆盖当前行就可能丢失左上的旧值。通常用两个临时变量保存左上方和左边的旧值或者干脆不加优化先写完整二维ac后再考虑空间优化。这类双序列问题的核心经验是把两个序列的长度作为两个维度写进状态状态转移就是“当前字符匹配/不匹配”的分支讨论。凡是“两个字符串/数组之间找关系”的题八成都可以尝试双序列DP。3. 背包问题模型01背包、完全背包与滚动数组3.1 01背包的状态设计与转移推导01背包是动态规划里最经典的模型之一。每件物品只有取或不取两种选择目标是背包容量有限时获得最大总价值。洛谷题单里的采药、开心的金明hot100里的分割等和子集底层都是01背包。先说标准定义有n个物品第i个物品重量为w[i]价值为v[i]背包总容量为C。定义dp[i][j]表示考虑前i个物品当前背包容量为j时能获得的最大价值。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 当j w[i] dp[i][j] dp[i-1][j] 当j w[i]第一个max里dp[i-1][j]是不取第i个物品dp[i-1][j-w[i]] v[i]是取第i个物品先腾出w[i]的容量再放进去。这里为什么要用i-1状态因为01背包要求每个物品只能选一次不能在同一轮里复用同一个物品所以必须参考上一轮的处理结果。图示化思考整个dp表是一个n×C的矩阵i方向是物品顺序j方向是容量。每个格子的值只由它上面一行同一列和左上方某个格子的值决定。方向明确代码就好写了。3.2 滚动数组优化与遍历顺序的“禁忌”很多新手优化背包空间把二维dp压成一维dp[j]后发现结果莫名其妙变了。原因就出在遍历顺序上。一维优化的标准写法for i in 1..n: for j in C..w[i]: # 注意从大到小 dp[j] max(dp[j], dp[j-w[i]] v[i])为什么j要从大到小遍历因为一维dp[j]在更新时dp[j-w[i]]必须仍然是“上一轮i-1”的结果而不能是当前轮已经更新过的结果。如果j从小到大遍历dp[j-w[i]]可能刚被本轮更新过相当于同一个物品被选了多次这就不再是01背包变成完全背包了。这是动态规划题目里最经典的“顺序陷阱”没有之一。我踩过这个坑两次之后总结了一个记忆方法01背包是“从大到小偷着更新”完全背包是“从小到大正大光明更新”。把这个顺口溜记下来背包题基本不会因为遍历方向再出问题。3.3 完全背包与多重背包的差异完全背包表示每个物品可以无限取用转移方程看似一样只是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])关键区别在于取第i个物品后剩余部分依然可以考虑再次取第i个物品所以依赖的是当前行dp[i][j-w[i]]而不是上一行dp[i-1][...]。用一维数组写的时候j从小到大遍历正好能利用本行已经更新的值实现“无限复用”。多重背包则介于二者之间每个物品有数量限制count[i]。如果count很大可以二进制拆分把多个相同物品拆成1、2、4...份转成01背包处理。这样做的正确性在于任意数量都可以由这些二进制分组组合出来而拆出的每一组又只能取一次恰好符合01背包的约束。做题时首先要判断每个物品可用的次数一次01、无限次完全包、有限次多重宝。这个判断错了遍历顺序也就跟着错最后的dp表全乱。建议每次写背包题前在注释里写清“类型遍历方向”习惯养成就很少翻车。4. 从算法题到工程车辆动态规划问题中的DP思想4.1 车辆调度为什么能抽象成DP算法题里的DP刷多了会发现真实工程中的很多问题也带着DP的影子车辆动态规划就是典型例子。这里说的“车辆动态规划问题”不是某一个具体题目而是一大类资源调度优化问题比如配送车辆路径选择、出租车调度、共享汽车投放本质都是在容量、时间、里程等约束下对“车辆”这个资源做最优分配。我们用一个简化场景说明一辆车从起点出发要依次服务若干客户点每个点有最早服务时间和最晚服务时间车辆有载重上限问最多能服务多少个点或者总行驶距离最短。这很像时间窗约束下的路径问题完整解决需要组合优化算法但可以考虑用DP处理其中一部分。比如假设路线顺序已经确定那么“当前到达某个点时剩余多少时间、还能接多少货”就可以作为状态做容量限制下的收益最大化这就是一个带时间约束的背包。更常见的是“车辆数目运输任务分配”问题多辆车分别装载不同货物每辆车容量有限希望总成本最小这种分配问题可以直接建模成多维背包每件货物选或不选每辆车对应一个容量维度。4.2 用多维背包模拟车辆装载问题假设有三辆车容量分别是C1、C2、C3有n件货物每件重量w[i]、运送价值v[i]每件货物必须由某一辆车运输且每辆车的总重量不能超载目标是最大化总运送价值。这就是一个三维背包dp[a][b][c]表示三辆车分别已用容量a、b、c时的最大价值。每件货物依次决策分别尝试放入第一辆、第二辆、第三辆或者不放。转移dp[a][b][c] max(dp[a][b][c], dp[a-w[i]][b][c] v[i] if aw[i], dp[a][b-w[i]][c] v[i] if bw[i], dp[a][b][c-w[i]] v[i] if cw[i])用滚动数组写的时候三个维度都要从大到小遍历原理和01背包一维优化完全一样保证每件货物只被考虑一次。实际工程里维度可能更多比如还要加时间窗、冷热链、司机休息时间维度一多DP表会指数膨胀这时就需要换成启发式算法或列生成。不过这不代表DP思想没有用恰恰相反很多启发式算法在局部优化阶段还是会用DP做“容量分配”的子模块所以算法题里练好的背包模型在工程项目里是能直接迁移的基础能力。4.3 DP落地的工程注意事项真实车辆动态规划问题和刷题有几个明显差别值得特别提醒维度爆炸动态规划表的大小随着状态维度指数增长三辆车可能还勉强十辆车就没法直接开三维数组了。工程上要么压缩状态要么放弃精确DP用近似方法。边界条件复杂车辆路径问题里“容量”“时间窗”“服务时间”相互耦合状态必须定义得更细否则漏掉约束会导致结果不可用。性能要求线上系统往往要求毫秒级响应DP如果规模太大需要配合剪枝、预处理和空间压缩。我见过一个团队直接把算法竞赛的二维背包代码搬上生产环境结果输入一变成百辆车就内存爆掉。后来他们用贪心先排一个初始解再用DP只优化几个关键环节才把效果和性能都平衡下来。这个经验很重要工程里DP是解决问题的工具之一不是非要满状态求解才算用DP。5. hot100视角动态规划高频题与常见错误自查5.1 高频DP题型的模型映射把LeetCode hot100里和DP相关的题目过一遍会发现它们绝大多数能归入前文提到的模型。这里做一张映射表供自查题目类型核心模型状态定义爬楼梯线性递推dp[i]表示到达第i阶的方法数最大子序和线性DPdp[i]表示以i结尾的最大子段和打家劫舍线性DPdp[i]表示前i间房能偷到的最大值最长递增子序列线性DPdp[i]表示以i结尾的LIS长度分割等和子集01背包dp[j]表示是否能用元素凑出和j零钱兑换完全背包dp[j]表示凑出金额j的最少硬币数编辑距离双序列DPdp[i][j]表示A前i个字符到B前j个字符的编辑距离看到题目先对号入座能少走很多弯路。很多人喜欢直接凭感觉写写到一半发现状态不全推倒重来其实花一分钟先想清楚模型后面反而快很多。5.2 初始化与边界最容易翻车的地方刷了这么多题我总结的DP错误里初始化错误占比远超转移方程错误。常见问题包括求最大值却把dp数组初始化为0导致负权路径被错误忽略。正确做法是针对求解目标求最大值时非法状态用负无穷如-1e9求最小值时用正无穷如1e9。边界漏算。比如dp[0]到底代表“空集合”还是“第一个元素”这个问题必须想清楚。像分割等和子集dp[0]要置为true表示空集能凑出0其他置为false。字符串数组从0还是从1开始。如果从0读入转移时dp[i-1]可能出现负数下标建议统一把数据下标后退一位dp数组多开一位。我自己每次写完DP都会做三个边界测试空输入、最小规模、最大规模。比如n1时答案是什么C0或者容量为0时dp表变化是否符合预期这些测试虽然简单却经常能揪出初始化问题。5.3 调试DP的实用手段打表与对比调试DP最有效的办法不是单步跟踪而是把dp表完整打出来逐行检查是否合理。我通常会在关键转移后加一段临时输出for i in range(1, n1): for j in range(1, C1): print(dp[i][j], end ) print()然后拿一个非常小的样例手工推算一遍DP表把推出来的表格和程序输出对比。只要某个格子对不上就顺着它背后的转移链往回找问题基本都能定位。这条方法虽然土但比任何调试器都好用。另一个技巧是写一个暴力解法的对拍器DP写完后用随机数据让两组代码同时跑结果不一致就不断缩小数据规模。我在刷hot100时经常这么干特别是转移方向容易混的背包题对拍能节省大量手动验算时间。5.4 动态规划学习路径的建议八期内容走到这里如果还想继续往前推进我给一条实操路径。第一把线性DP和背包彻底吃透。这两块像动态规划的地基把状态设计、滚动数组、初始化这些基本功练熟其他模型都是延展。第二顺着洛谷题单刷题每一道题都要能说出三个东西状态定义、转移方程、边界条件。不能说出这三样说明这道题还没真正掌握哪怕AC了也是背模板。第三利用hot100查漏补缺。hot100里的DP题相比洛谷更偏工程思维题目描述更接近真实问题场景能把模型从竞赛转换为落地很有价值。第四学有余力再拓展区间DP、状态压缩DP、树形DP。前七期内容已经把树形DP和数位DP铺垫过了这一期主要是把公共主线串一遍后面可以针对薄弱模型再各写专题。我自己到现在写DP依然会在草稿纸上先写清“dp[i][j]代表什么”再动代码。这一步看起来多花三分钟但能防止后面半小时的无效调试。状态定义清晰转移方程基本是水到渠成的事。最后分享一个小经验遇到一个新问题先别急着套模型试试把题目改成“有一组选项、每个选项消耗资源且带来收益、总资源有限”的描述如果改得顺多半就是背包改成“从前往后依次处理每个位置当前状态只依赖前几个位置”多半就是线性DP。这套判断思路在车辆动态规划和hot100里都帮我快速定过方向。希望这一篇也能让你在DP这条路上少踩几个坑多几分确定性。
