[kuangbin带你飞]专题十二 基础DP1 题解总结入坑动态规划大部分人死在了状态定义和转移方程上刷完专题十二这个感觉特别明显。这个专题是DP入门非常好的第一份练习材料题量不大但覆盖了线性DP、背包、LIS、LCS、双序列DP、二维DP这些最核心的模型而且每道题都不会给你堆一堆花里胡哨的操作老老实实把状态想清楚就能过。我自己的体会是不要急着看题解先自己推状态和方程推不出来再对照题解找卡点这样刷完一遍后面做区间DP、树形DP、状压DP都会轻松很多。专栏设置里没有难度分级的说法但从实战体感来看前几道是纯粹的入门热身中间开始上强度最后几道需要一些思维量。这篇文章我把每道题的核心思想、状态定义、转移方程、初始化细节、遍历顺序和易错点全部整理出来最后给一份通用的刷题总结和调试技巧。所有代码均以C为参考语言题解中的数组下标如果没特别说明一律从1开始。1. 内容整体设计与思路拆解1.1 这个专题到底在练什么基础DP1的核心目的只有一个让你学会用“状态”描述问题用“转移”表达决策。专题里的题几乎都不会考你冷门的优化技巧二分优化LIS已经算最进阶的操作了但就算不会二分靠O(n²)的朴素DP也能把题过掉。这说明专题的重心不是炫技而是让你把DP的基本功打扎实。学习路径上是递进的前几道题训练的是线性DP状态基本就是“处理到第i个位置时某种含义下的最优值”转移来自上一个位置或之前某个位置中间几道题加入了“选择”的概念也就是背包模型的雏形你需要学会“取”与“不取”两种决策后段题目开始涉及双序列DPLCS变种、双串匹配都是这类收尾题有一些二维DP和需要排序预处理的题考察的是“先排序再用DP”的经典套路。刷完之后你回头看其实所有题都逃不开那三板斧状态定义、状态转移方程、初始化与边界处理。1.2 状态定义与转移方程的设计方法很多初学者拿到DP题第一反应是“我不会定义状态”。实际上定义状态有规律可循核心是抓住题目问的是什么以及有哪些维度的信息会影响答案。拿“数列变递增最少删几个数”这一类问题举例。题目问的是最少删除数量稍微转化一下就是“最多保留多少个”于是状态定义就变成了“以第i个元素结尾的最长上升子序列长度”。这就是经典LIS看起来难实际就是把“删除”转化成了“保留”。再比如“从左上角走到右下角路径上收集最大值”这类网格DP状态一定是二维的dp[i][j]表示走到第i行第j列时的最大值。为什么是二维因为影响答案的变量就是当前的坐标行、列各占一维。凡是网格上的DP二维起点几乎永远是这个。我自己用过一个很管用的方法把题目中的“选择”“位置”“剩余容量”“上一个状态”这些词先列出来每个词对应一维然后照着维度写dp数组。比如背包问题是“前i件物品、剩余容量j”LCS是“A串前i位、B串前j位”维度就是这么来的。1.3 为什么题目顺序是精心安排的认真刷完会发现题目顺序基本按“单一决策 - 双决策 - 预处理决策”来安排先来最简单的线性递推让你感受“状态”和“转移”是什么东西再来LIS、LCS这种有明确方程模板的题让你背熟经典模型然后用背包和二维DP这类需要自己融会贯通的题逼你脱离模板最后上一道“最长公共上升子序列”这种综合题把两个模型合在一起用。按这个顺序刷完全不用额外找其他题单直接能在脑子里形成一条清晰的DP知识链。建议每道题AC之后都在草稿纸上重新默写一遍转移方程和复杂度这个动作坚持下来到了区间DP和树形DP你会感谢自己。2. 核心细节解析与实操要点2.1 专题涉及的DP模型一览先把专题涉及的核心模型列个表后面逐题拆解的时候心里就有谱了模型状态定义常用形式复杂度级别典型特征线性递推dp[i] 表示第 i 个状态的最优值O(n)转移只依赖前几个状态最长上升子序列 LISdp[i] 表示以第 i 个元素结尾的LIS长度O(n²) 朴素 / O(n log n) 二分二维循环比较大小最长公共子序列 LCSdp[i][j] 表示 A 前 i 位与 B 前 j 位的LCS长度O(nm)双串匹配逐字符比较最长公共上升子序列 LCISdp[i][j] 表示 A 前 i 位与 B 前 j 位的LCIS长度O(nm)LCS与LIS结合体01背包dp[j] 表示容量 j 能获得的最大价值O(nV)逆序更新容量二维网格DPdp[i][j] 表示到达 (i,j) 的最优值O(nm)上/左方向转移专题里的题基本就是这些模型的套壳变形识别出母模型之后方程的推导就只是套参数。2.2 初始化与边界处理DP最容易翻车的地方说句实在话转移方程写错的人其实不多十个WA里有八个是初始化写错了或者是数组开小了或者是边界情况没考虑。我自己踩坑总结出几个规律第一dp数组的初始值通常要区分“非法状态”和“合法状态”。比如LIS里dp[i]最短也是1因为每个元素自身就构成一个长度为1的上升子序列所以初始化全部为1而背包里dp[0]0表示容量为0时价值为0其余初始化为负无穷或0要看题目是求最大还是最小。第二滚动数组使用前要确认上一维的值是否还在。我见过不少朋友写一维背包时内层循环顺序写反结果同一个物品被装了无数次这种错误特别隐蔽。第三多组输入时dp数组一定要重置。别觉得上一组数据算完不影响下一组初始化漏了这题直接WA到怀疑人生。提示DP题WA之后第一件事不是改方程而是检查初始化。我至少有一半的DP罚时都花在了这种低级问题上。2.3 遍历顺序的底层逻辑“为什么背包内层循环要倒序” 这个问题问过很多次答案其实是为了保证每个物品只取一次。正序遍历时dp[j-w[i]]可能在当前这一轮已经被更新过也就是同一个i被用了多次这就变成了完全背包倒序遍历时dp[j-w[i]]还是上一轮的旧值保证每个物品只贡献一次。而完全背包则正好反过来内层正序遍历让同一个物品可以被反复取。网格DP也有类似的逻辑如果状态只能从“上方”和“左方”转移那么按行从小到大、列从小到大遍历即可因为计算dp[i][j]时dp[i-1][j]和dp[i][j-1]必然已经算完了。这些东西光看结论没用自己改一遍代码看结果差异印象就深了。3. 实操过程与核心环节实现3.1 热身题基础递推与简单状态先从最基础的热身题说起。这类题的特征是dp[i]只依赖前一两项几乎没有选择分支用来入门非常合适。典型题一爬台阶问题。 题目大意一个人上台阶一次可以跨1级或2级问上到第n级台阶有多少种不同走法。状态定义dp[i]表示上到第i级台阶的走法总数。 转移方程dp[i] dp[i-1] dp[i-2]。 初始化dp[1] 1dp[2] 2。这题本身没什么难度但它告诉了初学者一个很重要的概念dp[i]代表的是“走到第i个状态”的方案数转移就是把所有能到达当前状态的路径加起来。典型题二数字三角形。 题目大意给出一个数字三角形从顶部出发每次可以走到下一层相邻的两个位置之一问从顶部走到底部的路径上数字之和最大是多少。状态定义dp[i][j]表示走到第i层第j个位置时的最大路径和。 转移方程dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]。 初始化dp[1][1] a[1][1]然后从第2层开始逐层计算。这题的特点是“路径选择”直接展现在方程里是后续网格DP的基础。解题时需要特别注意边界位置比如每行第1个位置只能从左上转移最后一个位置只能从正上方转移可以特判也可以把非法位置置为负无穷。3.2 经典模型最长上升子序列 LIS题目大意给定一个长度为n的序列求最长严格上升子序列的长度。状态定义dp[i]表示以第i个元素结尾的最长上升子序列长度。 转移方程dp[i] max(dp[i] , dp[j] 1) 其中 j i 且 a[j] a[i]。 初始化dp[i]全部初始化为1因为每个元素自己单独就是一个长度为1的上升子序列。朴素实现如下#include bits/stdc.h using namespace std; int a[1005], dp[1005]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; int ans 0; for (int i 1; i n; i) { dp[i] 1; for (int j 1; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans endl; return 0; }这题有个值得注意的细节题目要求的是“严格”上升所以比较时必须用 a[j] a[i]如果允许相等就是 这是很多初学者容易忽略导致WA的点。另外有的变种题会问“最少删除多少个数使得序列变成严格递增的”答案就是 n - LIS长度。这个转化思路在专题后面会出现值得记下来。LIS还有一个O(n log n)的二分优化方案用dp数组维护当前上升子序列的末尾最小值然后用lower_bound找插入位置。不过专题本身用朴素O(n²)完全够如果以后做更复杂的题再上优化。3.3 经典模型最长公共子序列 LCS题目大意给定两个字符串A和B求它们的最长公共子序列长度子序列可以不连续但要保持相对顺序。状态定义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])。初始化dp[0][j]和dp[i][0]都为0表示空串与任何串的LCS长度为0。#include bits/stdc.h using namespace std; char a[1005], b[1005]; int dp[1005][1005]; int main() { while (scanf(%s %s, a 1, b 1) ! EOF) { int n strlen(a 1), m strlen(b 1); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i] b[j]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } printf(%d\n, dp[n][m]); } return 0; }LCS的精髓在于“当前字符相等”和“当前字符不等”两种情况的处理。相等时两个字符都可以选直接在前一个公共子序列上延长一位不等时至少有一个字符不能选取删掉A当前字符或删掉B当前字符中更好的结果。这里有一个很容易犯的错把dp[i][j]和dp[i-1][j-1]当成了所有转移的唯一来源。很多人会写成 if 相等dp[i][j]dp[i-1][j-1]1else dp[i][j]max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])其实else里dp[i-1][j-1]一定 ≤ max(dp[i-1][j], dp[i][j-1])所以没有必要特判中间项。直接把else写成max(dp[i-1][j], dp[i][j-1])就行。3.4 双序列DP最长公共上升子序列 LCIS题目大意给定两个序列A和B求它们的最长公共上升子序列长度也就是既是公共子序列又是上升序列的最长串。这是专题里思维量比较大的一道题需要同时结合LCS和LIS的思想。整体的思考过程可以这样拆第一步因为是双序列状态至少两维dp[i][j]表示A序列前i项和B序列前j项中以B[j]结尾的LCIS长度。为什么要用B[j]结尾而不是A[i]结尾这是很多人的第一个卡点。这里的核心原因是我们总要枚举“选了哪个数作为当前子序列的最后一个元素”而公共子序列中如果最后一个元素是B[j]对应的也必须是A中的某个相等元素用B[j]做结尾描述更直观。第二步考虑A[i]与B[j]的关系如果A[i] ! B[j]那么A[i]不能作为这个公共上升子序列的最后一个元素所以dp[i][j] dp[i-1][j]如果A[i] B[j]说明我们可以把A[i]同时也等于B[j]作为子序列的结尾那么需要在A的前i-1项里找一个比B[j]小的B[k]作为倒数第二个元素即 dp[i][j] max(dp[i-1][k]) 1 其中1 ≤ k j 且 B[k] B[j]。把上面整理成代码#include bits/stdc.h using namespace std; const int N 505; int a[N], b[N]; int dp[N][N]; int main() { int T; scanf(%d, T); while (T--) { int n, m; scanf(%d, n); for (int i 1; i n; i) scanf(%d, a[i]); scanf(%d, m); for (int i 1; i m; i) scanf(%d, b[i]); memset(dp, 0, sizeof(dp)); for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] dp[i-1][j]; if (a[i] b[j]) { int mx 0; for (int k 1; k j; k) { if (b[k] b[j]) mx max(mx, dp[i-1][k]); } dp[i][j] max(dp[i][j], mx 1); } } } int ans 0; for (int j 1; j m; j) ans max(ans, dp[n][j]); printf(%d\n, ans); } return 0; }这个朴素实现是O(n * m * m)的数据范围一上来就会超时需要优化。优化的思路是在枚举j的过程中实时记录一个mx值当遍历到j时如果满足b[k] a[i]因为此时a[i]b[j]所以也就是b[k] b[j]就更新mx max(mx, dp[i-1][k])。这样内层就不需要再枚举k了复杂度降到O(n*m)。for (int i 1; i n; i) { int mx 0; for (int j 1; j m; j) { dp[i][j] dp[i-1][j]; if (b[j] a[i]) mx max(mx, dp[i-1][j]); if (a[i] b[j]) dp[i][j] max(dp[i][j], mx 1); } }等等这里有个容易绕晕的点为什么更新mx的条件是b[j] a[i]而不是b[j] b[j]这显然是废话因为我们想维护的是“当前所有满足值小于a[i]的B前缀位置j其dp[i-1][j]的最大值”。等遇到a[i]b[j]时这个mx正好就是“小于当前结尾值的所有前置LCIS长度最大值”从而得到dp[i][j]的最大值。注意LCIS的优化版本是专题里最有价值的一道题因为它的优化思路不是死记模板而是基于“在转移过程中维护一个滚动最大值”这个技巧在后续很多DP优化中会反复用到。3.5 背包基础01背包与完全背包专题里出现的背包题基本是01背包和完全背包的直接应用。01背包的经典描述有n件物品每件物品有重量w[i]和价值v[i]背包容量为V求能装下的最大价值。每种物品最多取一次。状态定义dp[i][j]表示前i件物品中选取若干件总重量不超过j时的最大价值。 转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。 意思是不取第i件继承前i-1件在容量j下的最大值取第i件就在容量j-w[i]的基础上加上v[i]。一维优化后的写法for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }内层倒序是01背包的灵魂前面已经说过原因。有个常见变种是“恰好装满背包”与“不超过容量”的区别如果要求恰好装满初始化dp[0]0dp[j]-INF(j0)如果只是不超过容量则全部初始化为0即可。这个细节在专题的某些题里会直接决定AC还是WA。完全背包的差别只有一处内层循环改为正序。含义是每个物品可以取无限次正序更新时dp[j-w[i]]可能在本轮已经被更新过相当于已经取过当前物品于是可以继续取。3.6 网格DP二维路径最大值网格DP的典型题题目大意是给定一个二维矩阵从左上角出发只能向右或向下走每个格子有一个价值求到达右下角时能获得的最大价值。状态定义dp[i][j]表示走到第i行第j列时的最大价值。 转移方程dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]。 初始化dp[1][1] a[1][1]第一行只能从左边来第一列只能从上面来可以先预处理也可以把边界外置为负无穷。这种题往往会出现“不能走某个格子”的变种处理方式是把这个格子的a值设为负无穷。还有一种变种是走两遍取两次用四维DP可以解决但专题里一般不至于那么狠主要还是练二维转移。另一个值得注意的网格DP变种是“最大子矩阵和”。解法是把列压缩成一维然后对每一行区间做一次最大子段和用前缀和优化到O(n^3)。这类题不在基础专题里但思路相通这里先不展开。3.7 偏序预处理型DP先排序再做DP专题中有一类题俯视下来是个二维偏序选择问题每个对象有两个属性要求选出一个集合使得一个属性单调递增另一个属性也满足某种顺序最后求某个最优值。这种题几乎都有一个共同套路先按一个属性排序然后在另一个属性上做LIS或LCS式的DP。举例说明。假设每个元素有高度h和重量w两个属性要求选出一个序列按h严格递增且w也严格递增求最长的选择长度。做法就是按h从小到大排序对排序后的序列在w上做LIS。但这里有一个致命细节如果排序后两个元素的h相同那么这两个元素在w上即使递增也不应该被同时选择因为它们不满足“h严格递增”。如果你贪图方便直接按h排序不处理相等情况会出现错误。解决办法是排序规则里当h相同时按w从大到小排。这样h相同的一组里后面的w一定比前面的小LIS就不会把h相等的两个元素都选进来。还有一种常见变种是元素之间的“包含关系”比如套娃娃、叠箱子同样可以排序后转LIS。这个套路理解透彻之后很多看起来复杂的题实际都是排序LIS的模板题。3.8 经典爬梯变种BB与DD的日常之走楼梯这里提一道偏生活化的递推题题目大意是一种游戏或日常行动规则描述核心仍然是线性DPdp[i]可以从dp[i-1]、dp[i-2]甚至dp[i-3]转移初始化略复杂要注意前几个位置的初值。题目本身不难练的是“把题意精确翻译成状态转移”的能力。实际做题时最需要注意的是不要想当然地把所有步长都写进去先看题目允许的上一状态有哪些再看有没有附加条件比如不能连续走某一种步长。有附加条件时往往需要加一维状态表示“当前使用的是哪种步长”。比如“不能连续走两步”这么一个简单限制就能让一维dp失效需要定义dp[i][0]和dp[i][1]分别表示“走到第i级且最后一步用的是走法0/走法1”这就是“加一维来消除后效性”的经典思路。专题虽然没有专门出一道这样的题但二维化思想在后面的LCIS和背包里都用到了值得提前理解。3.9 二维费用与多条件限制的变体有些题会同时存在两个限制条件比如既要限制总重量又要限制总体积这就是二维费用背包。状态定义直接加一维dp[j][k]表示容量达j且体积达k时的最大价值。转移方程也从max(dp[j][k], dp[j-w[i]][k-v[i]] val[i])来。另一种变体是“在满足A条件的前提下最大化B”比如选取若干元素使它们的“分数总和”最大但要求“重量和”不能超过某个阈值。这种题统一转成背包即可。专题本身对二维背包只是浅浅涉及但如果你把一维背包的循环顺序想明白了二维就是循环嵌套多一层逻辑上没有任何新东西。3.10 综合小题对偶问题与输出方案有几道题需要输出具体方案而不是只输出最优值。这种题一般需要额外开一个path数组记录每个状态是从哪个状态转移过来的最后从终态倒推回去。比如记录LCS路径时可以在转移时标记方向若A[i]B[j]方向记为1表示这个字符属于公共子序列若dp[i-1][j] dp[i][j-1]方向记为2表示来自上方否则方向记为3表示来自左方。输出时从dp[n][m]倒着走遇到方向1就把字符加入答案栈最后逆序输出。经验输出方案题的通用套路是先计算dp再倒推追溯路径。切忌在转移过程中边算边输出因为当前的最优决策依赖于后续状态顺推输出是错的。4. 常见问题与排查技巧实录4.1 常见WA原因与排查思路这里整理一份排错速查表基本覆盖了专题里绝大多数WA症状大概率原因排查方法答案偏小状态初始化成了0但最优值可能是负的检查是否应该初始化为-INF答案偏大背包内层循环顺序写反01写成完全检查循环顺序01背包必须倒序数组越界dp维度开小一维直接把数组开到极限5多组输入互相污染没有重置dp/ans每次while循环内memset严格/非严格上升搞混比较大小用了或确认题目要求是严格还是有等号边界状态算错没有处理第一行/第一列/第0项单独初始化边界或加哨兵TLE复杂度太高或memset过于频繁优化转移如LCIS滚动优化或减少重置范围4.2 我踩过的三个具体坑第一个坑是LCIS的优化。一开始按O(n * m * m)写样例过了但提交TLE当时还以为是常数问题。后来把mx维护进循环才明白这不是常数优化而是复杂度降了一个量级。这个教训提醒我当转移方程内层还要再套一层循环时多想想是否能用“扫描时维护一个最值”的办法降复杂度。第二个坑是LIS的严格递增。有一道题我把a[j] a[i]写成了a[j] a[i]样例输出看起来没什么问题但实际上把相等的数也计入了上升序列。这种错误很恶心因为小数据样例不一定能暴露问题只有大数据才WA。第三个坑是网格DP的边界。有一题第一行和第一列的处理我没特判直接把数组初始化为0结果从边界外“绕”进来的路径也变成了合法路径导致答案偏大。后来所有网格DP我都统一把dp初始化为负无穷只留dp[1][1]a[1][1]这样边界外永远是非法状态就不用每次特判了。4.3 状态压缩与滚动数组的内存技巧二维dp如果开不下可以先观察转移依赖的是上一行的值还是当前行的值。如果是上一行就可以用滚动数组只保留两行。比如LCS的dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]其中dp[i][j-1]是当前行dp[i-1][*]是上一行所以用两个一维数组就够。滚动数组的实现要注意更新顺序。如果dp[j]依赖dp[j-1]当前行和dp[j]上一行需要在更新dp[j]时dp[j]还是上一行的值不被当前行覆盖过。这通常是可行的因为j从小到大更新时dp[j]在更新前还是旧值。但如果转移依赖dp[j1]这种方向就要改变更新顺序。4.4 如何判断一维DP还是二维DP这一步用的是一套很朴素的判断标准题目只给了一个序列/一维状态且决策只和“当前位置”有关优先想一维dp题目给了两个序列或者一个序列两个维度位置限制优先想二维dp题目给了网格/矩阵默认二维dp起步题目有“选择”和“限制”两个约束比如选物品容量限制优先想背包。维度并不是越少越好而是恰好够描述所有影响答案的信息。如果你发现dp状态少了一维那大概率是漏掉了一个关键信息做题的时候需要回头重新审视题目条件。4.5 一组实用的自测数据设计技巧DP写完以后样例过了别急着交先在本地跑几组自测数据。我用过比较有效的方法是对于LIS/LCS构造全递增、全递减、全相等、随机混合这四种数据验证边界条件对于背包构造容量刚好等于某件物品重量、容量小于所有物品、容量远大于总重量这几种情况对于网格DP构造1行n列、n行1列、全是负数这三种极端情况看边界处理是否仍然正确。负数数据特别关键因为很多初始化用的是0如果答案是负数0初始化就直接WA了。5. 刷题顺序与进阶路线建议5.1 专题在整体DP学习中的定位基础DP1的定位是“从0到1”它不要求你掌握复杂优化但要求你彻底理解状态定义与转移。刷完后你会形成一个重要的认知所有DP题都可以用“状态-转移-初始化-遍历顺序”这个框架去套。接下来推荐的学习路线是先巩固本专题的每一个模型做到看一眼题就能判断属于哪种模型的程度再做区间DP理解“合并类”DP的状态设计与枚举方式然后刷树形DP学会在树上做DP这部分多了一个“子树合并”的概念最后再碰状压DP和数位DP这两块需要前面所有基础都扎实了才好上手。如果跳过基础直接做状压大概率会被位运算和状态枚举劝退所以这个专题一定不要赶进度做懂比做快重要。5.2 一个高效的二刷计划一刷可以按题目顺序做目的是“见识模型”。二刷时建议按模型分类做把同类题放一块比较第一天线性递推 数字三角形各写两遍代码第二天LIS LCS重点推导方程并尝试输出路径第三天背包全部题型训练一维滚动数组与各种循环顺序第四天LCIS优化版以及排序LIS的套路题第五天把四天做过所有题的转移方程默写在纸上闭卷推导。二刷还有一个小技巧是每道题尝试用与第一次不同的一维/二维写法实现比如LIS用二分优化LCS用滚动数组背包用记忆化搜索写一遍。这种方法能逼你理解这个状态到底是怎么被“记住”和“继承”的算是把DP从术的层面提升到道的层面。5.3 路径追溯与方案输出专题如果想进一步强化路径输出能力可以自己改几道题重新做一遍把LIS改成输出最长上升子序列LCS改成输出最长公共子序列背包改成输出选取了哪些物品。改题练习能直接检测你是否真的理解了状态来源比单纯刷AC数量有效得多。具体操作是转移时同时更新一个结构体数组pre[i][j]记录“当前状态来自哪里”最后从终态反向走回去。这种练习非常适合面试前突击因为输出方案在笔试里经常出现。6. 写在最后的实战心得6.1 做题时的思考顺序模板总结一下我刷这个专题沉淀下来的思考模板每拿到一道DP题都按这个顺序来第一步识别题目归属的DP模型。是线性、LIS、LCS、背包还是网格题如果识别不出来就用“我有哪些约束条件”来分析。第二步定义状态。用一句“dp[i][j]表示……的最优值/方案数/可行性”写清楚每个维度的含义写完默读一遍看看是否覆盖了题目所有关键信息。第三步写转移方程。核心是思考“当前状态能从哪些前面的状态转移过来”把所有来源列出再配一个max/min或加法。第四步设定初始化和边界。写出dp[0]或者dp[1]的初始值以及边界位置的特殊处理。第五步确定遍历顺序。思考计算dp[i][j]时用到的子状态是否已经计算完毕。这个模板看起来很简单但真正执行到位并不容易。很多题卡住都不是因为算法难而是因为少做了一步比如“按题目要求排序”这一步没做哪怕后面方程全对也无济于事。6.2 个人建议与容易忽视的习惯我强烈建议每做完一道题在代码旁边用两行注释写下“我的状态定义”和“我的转移方程”。别觉得多余很多人在专题刷完一周后再回来看当时的代码已经完全想不起dp[i][j]是什么意思了注释能帮你快速复盘。再提一个容易忽视的习惯看好数据范围再开数组。有些题n可以到几千甚至上万O(n²)的DP会超时这时候就要想是不是有O(n log n)解法或者问题是不是可以用贪心解决。盲目套DP也是很多人的通病。另外调试DP问题时可以打印整个dp数组。以内层循环为顺序逐行输出能直观看到哪个状态的值不合理。比如LIS的dp数组如果出现“非递减序列中间突然变小”的现象就知道方程或初始化哪里出了问题。6.3 最后一个实用小技巧写lc[i]或dp数组时我习惯用print对拍的方式验算小规模数据写一个暴力枚举的解法和DP解法跑同样的小范围随机数据输出不一致就去排查。暴力解法虽然慢但它正确性一目了然在对拍时能快速定位到出错的状态或转移。这个习惯我从基础专题一直用到了后面的树形DP和状压DP每次遇到复杂的DP题先暴力后DP做对拍基本都能在几分钟内找到问题。建议你也养成这个习惯它比肉眼盯代码排查效率高太多了。最后再分享一点感受DP的学习曲线是陡峭的可能做前三道题的时候还会觉得“就这”但到LCIS和排序LIS组合题就会明显感觉到压力。这个时候千万别泄气这恰恰说明你的思维正在从“套模板”向“设计算法”转变。把每一道卡了很久的题理解透彻比连续水过十道简单题有用得多。基础DP1这二十来道题我刷了两遍第一遍只求AC第二遍才真正理解每个转移方程背后的“为什么”也是从第二遍开始我觉得自己算是踏进了动态规划的门。