1. 为什么“动态规划9”值得单独写一篇动态规划DP大概是算法学习路上最让人又爱又恨的东西。爱的是它一旦想通很多看似复杂的题目就是几行状态转移的事恨的是“想通”这个过程极其折磨状态怎么设、转移怎么推、边界怎么处理每一步都可能卡到你怀疑人生。我刷过不少题也带过一些新人发现大家在DP上踩的坑几乎一模一样拿到题不知道用不用DP用了DP又不知道状态怎么定义状态定义好了又写不出转移方程方程写出来了又爆内存或者超时。“动态规划9”这个标题说的不是某一道题而是我整理的一套面向实战的DP学习路径——用9道经典题、9个核心模型、9个高频考点把动态规划从头到尾串一遍。整套内容围绕线性DP、区间DP、背包DP、树形DP、状压DP这几个主力模型展开每个模型都会拆到“为什么这么想”“转移方程怎么来的”“代码怎么写才对”“洛谷原题去哪找”这个粒度。适合刚学完基础语法、准备系统性刷DP的读者也适合刷了不少题但总觉得“一换新题就不会”的人。这套东西背后其实有一个判断动态规划不是一个靠题海战术就能堆出来的技能它更像一个“模型库套路库”。你脑子里的模型越多、套路越清晰看到新题的时候能做的联想就越快。所以这篇文章的重点不是罗列题解而是把模型和套路讲透让你以后再遇到DP题至少知道往哪个方向想。2. 动态规划的模型原理四个要素和一个本质2.1 动态规划到底在“规划”什么很多初学者对DP的第一印象是“递推加记忆化”这个印象没错但不够。你去看那些DP写得非常顺的人他们脑子里想的其实是一个四件套状态定义、状态转移、初始化、遍历顺序。四者缺一个代码就跑不对四个都想清楚代码基本就是照着填空。先说状态定义。状态就是你用一组变量去描述“当前局面”的最小集合。比如斐波那契数列F(n)这个状态描述的就是“第n项的值”爬楼梯问题里dp[i]描述“爬到第i级台阶有几种方法”。状态定义是整个DP的根基因为后续的所有转移都是在这个定义上展开的。初学者最容易犯的毛病就是状态定义得太大——比如把一整个数组的情况都塞进一个状态里结果转移写不出来或者定义得太小——漏掉了某个对决策有影响的变量结果答案算错。判断状态定义是否合理有一个很朴素的标准给定当前状态未来的决策不再依赖过去的具体路径只依赖当前状态本身——这就是所谓的“无后效性”。然后是转移方程。转移方程描述的是“从当前状态到下一个状态的变化规则”。它必须覆盖所有可能的决策路径同时不重复、不遗漏。你去看爬楼梯问题dp[i] dp[i-1] dp[i-2]它的逻辑就是“最后一步要么跨一级、要么跨两级”这个观察把所有可能的上楼方式分成两类两类之和就是总数。这里的关键动作是“枚举最后一步”这是几乎所有DP题目的通用思路你不需要关心整个路径是怎么走过来的只需要关心从哪几个前驱状态能一步到达当前状态。再是初始化。初始化决定了DP的起点通常对应“规模最小的状态”。比如dp[1]1、dp[2]2或者最长递增子序列里每个位置至少长度为1。很多人写着写着就发现答案差1十有八九是初始化没写对。最后是遍历顺序。遍历顺序必须保证计算当前状态的时候它依赖的前驱状态已经被算过了。一维DP通常正着遍历背包DP里01背包要倒着遍历区间DP要先枚举长度再枚举起点——这些规律都可以从“依赖关系”反过来推导不用死记。2.2 最优子结构、无后效性与重叠子问题三个概念是干嘛用的教科书上会说动态规划能用的前提是“最优子结构”和“重叠子问题”。这两个词看着唬人说白了就一句话如果一个大问题的最优解可以由若干个子问题的最优解组合而成并且这些子问题会被反复计算那你就可以用DP把子问题的结果存下来避免重复计算。最优子结构的意思是“子问题最优组合起来就是全局最优”。最长上升子序列就是典型例子以第i个元素结尾的LIS长度等于所有满足nums[j] nums[i]的前缀LIS长度加1的最大值。你不需要知道那些前缀LIS具体是哪些元素只需要知道它们的最长长度因为长度这个信息已经完全决定了“后面还能不能接上”以及“接上之后有多长”。无后效性前面提到过指的是“过去的选择不影响未来的决策只影响当前状态的值”。这个性质非常重要因为如果未来决策还要考虑过去怎么走的细节那状态就要无限扩充DP就没法做了。重叠子问题就更直接斐波那契递归版会重复计算大量的F(n-1)、F(n-2)而DP自底向上只算一遍这就是那道经典“记忆化搜索改递推”的题要干的事。你可以把DP的思考流程压缩成四步先想能不能拆成子问题再想状态怎么定义再想转移方程最后想边界和遍历顺序。这套流程熟练之后你看到一道新题的第一反应就不会是“好难”而是“这道题的状态大概是……”。这就是模型化的价值。3. 线性DP专题从经典题到洛谷原题逐步拆解3.1 最长上升子序列LISO(n^2)与O(nlogn)两条路线性DP是动态规划里最基础的模型特征是状态沿着“序列下标”线性推进。洛谷上对应的经典题是P1020导弹拦截的LIS变形以及P1091合唱队形这类双端LIS组合题。先看最纯粹的LIS问题给一个数组求最长严格上升子序列的长度。O(n^2)写法是最直观的。定义dp[i]为“以第i个元素结尾的最长上升子序列长度”那么对每个i遍历所有j i如果nums[j] nums[i]就尝试用dp[j]1来更新dp[i]。状态转移是dp[i] max(dp[i], dp[j]1)答案就是所有dp[i]的最大值。初始化每个dp[i]1因为单个元素本身就是一个长度为1的上升子序列。复杂度O(n^2)n万级别以内没问题但是n到十万级别就超时了。O(nlogn)写法的核心思路是“贪心二分”但很多人初学时会觉得它不像DP。它的做法是维护一个数组dd[len]表示长度为len的上升子序列的最小末尾值。遍历每个元素x在d里二分找到第一个大于等于x的位置把它替换成x如果x比所有d值都大就说明可以接在现有最长子序列后面长度加一。这个做法本质上是在维护“让未来的上升空间最大”的策略。洛谷P1020的第一问就是LIS的O(nlogn)版第二问还要用上Dilworth定理转换成“不上升子序列的个数等于最长上升子序列的长度”这些细节如果感兴趣可以去找题目讨论区看。我实际刷题时的体验是O(n^2)写法必须熟练掌握因为它帮助你理解LIS的状态定义和转移逻辑O(nlogn)写法必须会用因为很多竞赛题的数据范围就卡在这里。两者不是互斥的而是同一个模型的两个视角。3.2 最长公共子序列LCS二维状态表是怎么推出来的LCS是线性DP里第一个让人感到“二维”的经典题。洛谷P1439就是一道LCS题而且P1439还给了“两个排列”这个特殊条件允许用映射转LIS的方式优化到O(nlogn)这个后面可以单独说。先看常规版本给两个字符串或序列A和B求它们的最长公共子序列长度。定义dp[i][j]为“A的前i个字符与B的前j个字符的最长公共子序列长度”。转移分两种情况如果A[i] B[j]那么这两个字符可以接在之前的最长公共子序列后面dp[i][j] dp[i-1][j-1] 1如果不相等那么当前状态只能从“不看A[i]”或“不看B[j]”两个方向继承dp[i][j] max(dp[i-1][j], dp[i][j-1])。你可以自己画一个二维表格行是A的每个字符列是B的每个字符然后一行一行地填。填表的过程你会直观地看到相等字符会让表格里的数字从左上角加1不相等的时候数字永远是左边和上边的最大值。这个过程跑通一遍你对“状态转移是沿着依赖方向推进”这句话就会有体感。复杂度O(nm)空间O(nm)不过可以用滚动数组优化到O(m)——因为每一行只依赖上一行和当前行左边很多题解里会这么干。有个细节要注意转移方程里if判断是否相等的分支和else分支是互斥的但如果你在相等分支只写了dp[i][j] dp[i-1][j-1]1而没取max会漏掉“即使相等也可能不如从左边/上边继承”的情况吗实际上不会漏原因在于dp[i-1][j-1]1一定不小于dp[i-1][j]和dp[i][j-1]——当然这个结论依赖字符相等时两者取的是各自的“前驱最优”。严格来说如果你想保证无懈可击可以在相等时也取三者max但大多数人不会写错。3.3 最大子段和、数字三角形最容易被小看的线性DP最大子段和洛谷P1115是一个看似特别简单、但非常能检验DP理解程度的题。定义dp[i]为“以第i个元素结尾的最大子段和”转移只有两个选择把当前元素接在dp[i-1]后面或者从当前元素重新开始。所以dp[i] max(dp[i-1] nums[i], nums[i])。答案就是所有dp[i]的最大值。这个题有意思的地方在于它跟“前缀和最小值”的做法殊途同归但用DP思维去理解能帮你建立“以什么什么结尾”这种状态定义的习惯。数字三角形洛谷P1216也是同样的道理。你从上往下走每次可以向左下或右下走求路径上和的最大值。正着做需要判断边界比较麻烦反着做就特别干净从最后一行开始dp[i][j] max(dp[i1][j], dp[i1][j1]) a[i][j]一路推到顶部就是答案。这个“自底向上”的遍历方向是很多树形/棋盘类DP的共同套路。你别小看P1216它几乎是后面所有“网格DP、树形DP”的雏形很多人做这题时觉得简单就跳过了结果学树形DP时状态转移就转不过弯来。我自己带新人刷题的时候总是建议先把P1115、P1216、P1020、P1439这四道题吃透再做其他线性DP的变体。原因很简单这四个题涵盖了“以i结尾”“二维表格”“前缀接续”“反推方向”这四种最常见的线性DP套路后面你遇到的大多数线性DP题都是这套东西的换皮。4. 区间DP、背包DP、树形与状压DP不止于线性4.1 区间DP先枚举长度再枚举起点最后枚举分割点区间DP描述的是“在一段区间上进行决策”的问题典型特征是状态是dp[l][r]表示区间[l,r]上某个最优值。洛谷最经典的区间DP题是P1880石子合并。问题是一排石子堆每次合并相邻两堆花费是两堆石子数之和问把所有石子合并成一堆的最小花费。这个题的状态定义很自然dp[l][r]表示合并第l堆到第r堆的最小花费。转移怎么想你把合并过程拆成“最后一步”——合并前一定有某个分界点k左边[l,k]已经合并成一堆右边[k1,r]已经合并成一堆最后这两堆再合并一次花费是sum[l][r]。所以dp[l][r] min(dp[l][k] dp[k1][r] sum[l][r])对所有k从l到r-1取最小。区间DP的遍历顺序特别讲究。你不能直接按l从1到n、r从l到n去填因为计算长区间的时候会用到短的区间但是如果你按起点枚举可能短的右区间还没算出来。标准做法是先枚举区间长度len从2到n再枚举左端点l右端点r llen-1最后枚举分割点k。这个顺序保证你算长区间的时候所有子区间长度都小于当前长度已经被算过了。空间复杂度O(n^2)时间复杂度O(n^3)n几百以内没问题再大就要想四边形不等式优化这是竞赛进阶内容不展开。P1880还有一个环形变体就是把石子堆摆成一个环首尾也能合并。解法是复制一遍数组把环形转化成链形枚举长度为n的窗口求最值。这个“复制翻倍破环成链”的技巧非常常用洛谷后面很多环状DP比如能量项链P1063也是这么干的。4.2 背包DP01背包为什么要倒序遍历完全背包为什么正序背包DP是动态规划里最“工业化”的一个分支因为它有固定模型01背包、完全背包、多重背包、分组背包、依赖背包。洛谷P1048采药是01背包入门题P1616疯狂的采药是完全背包入门题P1776宝物筛选是多重背包优化题。01背包的状态定义是dp[j]表示“容量为j的背包能装的最大价值”。转移是dp[j] max(dp[j], dp[j - w[i]] v[i])但这里有一个必须背下来的细节内层循环j必须从背包容量倒着遍历到w[i]。为什么因为dp[j-w[i]]这里用的必须是“还没考虑第i个物品”的状态。如果你正序遍历dp[j-w[i]]可能已经在当前物品的更新中被覆盖了等价于同一个物品用了多次——那就变成完全背包了。倒序遍历让每个物品最多被选一次这跟数组覆盖的顺序是严格对应的。完全背包的区别就在于内层循环正序遍历因为完全背包允许同一个物品选多次。你背这个规律的时候不要死记“01倒序、完全正序”要理解背后是“前驱状态是否可能已经被当前物品更新”。理解了这一点即使过了很久再写背包你也能从“语义”推导出遍历方向而不是凭记忆。多重背包P1776可以二进制拆分转01背包也可以单调队列优化。二进制拆分的思路是把数量为c的物品拆成1、2、4、8……这样一组物品每个新物品的重量和价值相应翻倍直到拆完。这样任意选法都可以用若干个拆出来的物品组合表示复杂度从O(c)降到O(log c)。你去看P1776的题解区几乎所有人都在用这个写法这是多重背包的标准答案。4.3 树形DP与状压DP两个进阶模型的核心套路树形DP的特征是状态在树的节点上定义转移从子节点向父节点汇总。洛谷P1352没有上司的舞会是最经典的入门题每个员工有快乐值如果选了某个节点它的直接子节点就不能选求能获得的最大快乐值。状态定义是dp[u][0]表示“不选u节点时以u为根子树的最大快乐值”dp[u][1]表示“选u节点时的最大快乐值”。转移就是dp[u][0]累加每个子节点的max(dp[v][0], dp[v][1])dp[u][1]则累加子节点的dp[v][0]再加自己的快乐值。这个题的套路能直接迁移到“树上最大独立集”“树上染色”等一系列题几乎每个树形DP初学者的第一题都是它。状压DP则是用二进制位表示集合状态典型场景是小规模的“选/不选”决策。洛谷P1879玉米田和P2704炮兵阵地是两道经典题。以P1879为例n和m都很小不超过12你可以把每一行的种植状态压缩成一个整数1表示种0表示不种然后枚举每一行所有合法状态通过与上一行的状态做“按位与为0”来避免上下相邻同时通过状态本身与“贫瘠土地”按位与为0来避免种到不能种的地方。状压DP的难点不在转移方程有多难而在于“怎么把一个方案表示成一个整数”。你习惯了位运算视角之后很多看似无从下手的题就会变成简单的状态枚举。5. 车辆动态规划问题当DP从刷题走进真实世界5.1 车辆路径规划里的DP影子“车辆动态规划问题”这个关键词其实是搜索引擎里真实存在的高频搜索词。普通人可能觉得动态规划只出现在竞赛题和期末考试里但事实上车辆路径规划就是DP的重要落地场景之一——比如物流配送里的路径规划、自动驾驶里的轨迹规划、共享单车调度里的最优分配这些系统内部都在用类似DP的思路求解。最简单的例子是“最短路径问题”的DP视角。从一个点走到另一个点经过若干中转站如果每个中转站之间的距离已知求总距离最短的路线。你可以定义dp[i][j]为“已经访问过i个点、当前位于第j个点的最短总距离”每次转移就是枚举下一个要去哪里。这正是动态规划在处理“多阶段决策”时的标准姿势把整个决策过程切成阶段每一阶段只根据当前状态做最优选择并且用状态值记住“从起点到当前状态的最优代价”。更进阶一些旅行商问题TSP是车辆路径规划里的经典难题它的典型解法就是状压DP。状态定义是dp[S][v]当前已经访问过的城市集合为S最后停留的城市是v求从起点出发访问完所有城市再回到起点的最短路径。转移就是枚举下一个没访问过的城市u尝试更新dp[S|(1u)][u]。n小的时候通常n ≤ 20这个解法非常实用复杂度O(2^n * n^2)。很多物流配送系统在做“多仓配货、路径合并”的时候底层算法就会用到这类模型。5.2 为什么说“车辆路径问题不能纯靠DP”不过我也要泼一盆冷水真实世界的车辆路径规划问题VRP通常不能直接用标准DP跑出结果。因为现实里有几十上百个配送点状态空间直接爆炸O(2^n * n^2)这种复杂度根本背不动。工程上更常见的做法是先用贪心、启发式算法比如最近邻、节约算法生成一个可行解再用模拟退火、遗传算法、禁忌搜索做局部优化或者用动态规划的思想做小规模子问题的精确求解比如“单辆车的最优配送顺序”“单个区域的最优分派组合”。这也是我特别想强调的一点学DP不是学一堆题解而是学一种“把问题拆成阶段、用状态记住代价、用转移连接决策”的通用能力。这种能力在真实系统中无处不在——数据库的查询优化、操作系统的资源调度、推荐系统的序列决策底层都有DP的影子。你如果在学习DP的过程中把“模型思维”练出来了走到哪个领域都不会吃亏。6. 洛谷动态规划题单9道题刷透DP的进阶路径6.1 题单总览与每道题的定位洛谷的动态规划题单在算法圈子里几乎是必刷清单。很多新人不知道怎么选题跟着题单走就是最省事的方式。围绕“动态规划9”这个主题我整理了一份9题清单从入门到进阶每一道题都对应一个独立模型题与题之间不重复、有递进关系。题目核心模型状态定义考点关键词P1216 数字三角形线性DP/网格DPdp[i][j]从底部到(i,j)的最大路径和自底向上、初始化P1115 最大子段和线性DPdp[i]以i结尾的最大子段和以“结尾”定义状态P1020 导弹拦截LISO(nlogn)d[len]长度len的最小末尾值贪心二分P1091 合唱队形LIS/LDS组合left[i]、right[i]双向LISP1439 最长公共子序列LCS/映射转LIS映射后求LIS特殊条件优化P1048 采药01背包dp[j]容量j的最大价值倒序遍历P1616 疯狂的采药完全背包dp[j]容量j的最大价值正序遍历P1880 石子合并区间DPdp[l][r]合并区间最优值长度遍历顺序P1352 没有上司的舞会树形DPdp[u][0/1]选/不选子树聚合6.2 刷题顺序与每道题的“验收标准”刷题不是做完就完每道题要有一个验收标准。比如P1216指标是你能在5分钟内写完且一次ACP1020要求你写出O(nlogn)版本并且说清楚为什么第二问的答案是“最长上升子序列的长度”P1439要求你能解释清楚“把排列映射成位置后为什么问题就变成了LIS”P1880要求你能默写出三层循环的模板并且知道为什么长度循环在最外面。我建议的顺序是P1216 - P1115 - P1048 - P1616 - P1020 - P1091 - P1439 - P1352 - P1880。这样从最简单的线性DP开始先建立“状态和转移”的感觉然后进入背包模型掌握遍历顺序再回到LIS/LCS这种经典线性DP加深理解最后挑战树形DP和区间DP。每一步都踩在上一步的基础上思维跨度不会太大不容易劝退。6.3 一个特别提示不要只刷“看懂”的题很多人刷题有一个误区只做自己一眼就知道怎么做的题遇到不会的题就跳过或者只看题解然后感觉“懂了”。这是刷DP题的大忌。DP题的价值恰恰在于“你想不出来”。你卡半小时然后再去看题解重点看的是“它怎么想到状态定义是这个”——这个思维过程才是你要学的。如果你每道题都能5分钟AC说明这套题对你来说太简单了该换更难的题单了。我个人的做法是一道DP题先独立想15到30分钟实在没思路再看题解看完题解后不急着写代码先自己把状态定义、转移方程、遍历顺序这三件事默写下来次日再独立重写一遍代码。这样过一遍比你一次AC十道简单题有用得多。7. 调试DP的实用技巧与常见问题实录7.1 输出中间状态DP调试的第一手段DP代码写出来跑出错误答案最常见的尴尬是“逻辑感觉没问题但答案不对”。这时候千万不要盯着代码硬看最好的办法是输出中间状态的dp数组。比如写LIS的时候把每个dp[i]打印出来你马上就能看到是不是某个位置的状态没更新对写背包的时候把dp[j]按容量从0到max打印成一行一行你就能直观看到物品放入的过程。我之前调试一个区间DP的变体题一直答案大了10排查了半天没看出来。后来我决定把每个dp[l][r]都打印出来对照手算的小例子一眼就发现是sum[l][r]算错了——我用了前缀和数组但更新的时候忘记加偏移量。这个错误如果靠读代码可能再读半小时也发现不了但输出中间状态一秒钟就能定位。7.2 常见错误Top 5与排查对照表在刷DP题的过程中有几类错误出现频率极高我把它们整理成了一个对照表你可以保存下来当排查手册用。错误表现可能原因排查方向答案比正确答案小状态初始化少了“至少为1”之类的基准检查dp数组初始化尤其LIS/LCS类答案比正确答案大状态转移重复计算或转移条件判断过宽检查if条件是否存在不该转移的路径结果正确但MLE高维dp数组开太大考虑滚动数组或压缩状态结果正确但TLEO(n^3)或更高复杂度超限考虑优化遍历、二分、单调队列01背包结果像完全背包内层循环用了正序遍历改为倒序遍历7.3 事不过三DP的“过题策略”最后分享一个刷题技巧。现在的在线评测平台比如洛谷都有“提交记录”和“题解区”。我的建议是一道DP题你提交超过3次还不过就停下来。不是说你写不出来而是说“硬碰硬”的效率太低。停下来做的事情是去看题解区的高赞题解重点看人家的“状态定义和转移方程”然后完全关闭题解自己重新写一遍代码。很多时候你差的不是代码能力而是“没想到状态可以这么定义”这个灵感而这个灵感靠死磕是磕不出来的。用这个方法我把洛谷的DP题单刷完一轮之后再回头看那些以前觉得“看不懂”的题基本都能在10分钟内理出思路。这就是模型化的力量——当你的脑子里有足够多的状态定义模板新题在你眼里就不再是“全新的”而是“某个旧模板的变体”。我个人在实际写代码的过程中还有一个习惯每道DP题AC之后我会在题解区看一眼别人有没有更巧妙的状态定义。这个动作看着不起眼但它能帮你积累“一题多解”的视野。很多时候一个更优雅的状态定义比一个AC的写法更能提升你的DP水平。