基础DP1刷题全解：状态定义与转移方程核心总结

[kuangbin带你飞]专题十二 基础DP1 题解+总结

入坑动态规划，大部分人死在了状态定义和转移方程上，刷完专题十二这个感觉特别明显。这个专题是DP入门非常好的第一份练习材料，题量不大，但覆盖了线性DP、背包、LIS、LCS、双序列DP、二维DP这些最核心的模型，而且每道题都不会给你堆一堆花里胡哨的操作，老老实实把状态想清楚就能过。我自己的体会是：不要急着看题解，先自己推状态和方程，推不出来再对照题解找卡点，这样刷完一遍，后面做区间DP、树形DP、状压DP都会轻松很多。

专栏设置里没有难度分级的说法，但从实战体感来看，前几道是纯粹的入门热身，中间开始上强度，最后几道需要一些思维量。这篇文章我把每道题的核心思想、状态定义、转移方程、初始化细节、遍历顺序和易错点全部整理出来，最后给一份通用的刷题总结和调试技巧。所有代码均以C++为参考语言，题解中的数组下标如果没特别说明，一律从1开始。

1. 内容整体设计与思路拆解

1.1 这个专题到底在练什么

基础DP1的核心目的只有一个：让你学会用“状态”描述问题，用“转移”表达决策。专题里的题几乎都不会考你冷门的优化技巧，二分优化LIS已经算最进阶的操作了，但就算不会二分，靠O(n²)的朴素DP也能把题过掉。这说明专题的重心不是炫技，而是让你把DP的基本功打扎实。

学习路径上是递进的：

• 前几道题训练的是线性DP，状态基本就是“处理到第i个位置时，某种含义下的最优值”，转移来自上一个位置或之前某个位置；
• 中间几道题加入了“选择”的概念，也就是背包模型的雏形，你需要学会“取”与“不取”两种决策；
• 后段题目开始涉及双序列DP，LCS变种、双串匹配都是这类；
• 收尾题有一些二维DP和需要排序预处理的题，考察的是“先排序再用DP”的经典套路。

刷完之后你回头看，其实所有题都逃不开那三板斧：状态定义、状态转移方程、初始化与边界处理。

1.2 状态定义与转移方程的设计方法

很多初学者拿到DP题第一反应是“我不会定义状态”。实际上定义状态有规律可循，核心是抓住题目问的是什么，以及有哪些维度的信息会影响答案。

拿“数列变递增最少删几个数”这一类问题举例。题目问的是最少删除数量，稍微转化一下就是“最多保留多少个”，于是状态定义就变成了“以第i个元素结尾的最长上升子序列长度”。这就是经典LIS，看起来难，实际就是把“删除”转化成了“保留”。

再比如“从左上角走到右下角，路径上收集最大值”这类网格DP，状态一定是二维的，dp[i][j]表示走到第i行第j列时的最大值。为什么是二维？因为影响答案的变量就是当前的坐标，行、列各占一维。凡是网格上的DP，二维起点几乎永远是这个。

我自己用过一个很管用的方法：把题目中的“选择”“位置”“剩余容量”“上一个状态”这些词先列出来，每个词对应一维，然后照着维度写dp数组。比如背包问题是“前i件物品、剩余容量j”，LCS是“A串前i位、B串前j位”，维度就是这么来的。

1.3 为什么题目顺序是精心安排的

认真刷完会发现，题目顺序基本按“单一决策 -> 双决策 -> 预处理决策”来安排：

1. 先来最简单的线性递推，让你感受“状态”和“转移”是什么东西；
2. 再来LIS、LCS这种有明确方程模板的题，让你背熟经典模型；
3. 然后用背包和二维DP这类需要自己融会贯通的题，逼你脱离模板；
4. 最后上一道“最长公共上升子序列”这种综合题，把两个模型合在一起用。

按这个顺序刷完全不用额外找其他题单，直接能在脑子里形成一条清晰的DP知识链。建议每道题AC之后都在草稿纸上重新默写一遍转移方程和复杂度，这个动作坚持下来，到了区间DP和树形DP你会感谢自己。

2. 核心细节解析与实操要点

2.1 专题涉及的DP模型一览

先把专题涉及的核心模型列个表，后面逐题拆解的时候心里就有谱了：

专题里的题基本就是这些模型的套壳变形，识别出母模型之后，方程的推导就只是套参数。

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] = 1，dp[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]+1，else 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]=0，dp[j]=-INF(j>0)；如果只是不超过容量，则全部初始化为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也严格递增，求最长的选择长度。做法就是：

1. 按h从小到大排序；
2. 对排序后的序列，在w上做LIS。

但这里有一个致命细节：如果排序后两个元素的h相同，那么这两个元素在w上即使递增，也不应该被同时选择，因为它们不满足“h严格递增”。如果你贪图方便直接按h排序不处理相等情况，会出现错误。解决办法是排序规则里，当h相同时，按w从大到小排。这样h相同的一组里，后面的w一定比前面的小，LIS就不会把h相等的两个元素都选进来。

还有一种常见变种，是元素之间的“包含关系”，比如套娃娃、叠箱子，同样可以排序后转LIS。这个套路理解透彻之后，很多看起来复杂的题实际都是排序+LIS的模板题。

3.8 经典爬梯变种：BB与DD的日常之走楼梯

这里提一道偏生活化的递推题，题目大意是一种游戏或日常行动规则描述，核心仍然是线性DP：dp[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：

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[j+1]这种方向，就要改变更新顺序。

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题都可以用“状态-转移-初始化-遍历顺序”这个框架去套。

接下来推荐的学习路线是：

1. 先巩固本专题的每一个模型，做到看一眼题就能判断属于哪种模型的程度；
2. 再做区间DP，理解“合并类”DP的状态设计与枚举方式；
3. 然后刷树形DP，学会在树上做DP，这部分多了一个“子树合并”的概念；
4. 最后再碰状压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，第二遍才真正理解每个转移方程背后的“为什么”，也是从第二遍开始，我觉得自己算是踏进了动态规划的门。