1. 动态规划入门到底在练什么很多人第一次接触动态规划Dynamic Programming简称DP的时候都会有一种每个字都认识连起来就不明白的感觉。状态转移方程摆在那里看题解能看懂自己上手就废。这不是你笨而是DP本身就是算法学习里的一道分水岭——它不像排序或者二分那样有固定的模板可以套它更像是一种思维方式需要你把大问题拆成小问题再从小问题的答案推出大问题的答案。DP练习-初阶题洛谷这个项目标题说白了就是在洛谷这个在线评测平台上刷动态规划的入门题目。洛谷是国内非常活跃的算法刷题社区题单体系做得很完善从入门到省选都有对应的训练路径。初阶DP题通常涵盖这几类线性DP、背包问题、区间DP的简单形式、树形DP的基础模型以及一些经典的递推问题。这个内容适合谁来参考如果你已经掌握了基本的循环、数组、递归但一看到求最优解计数方案数最长/最短这类问题就发怵那初阶DP题单就是为你准备的。如果你已经能独立做出大部分普及组难度的DP题但遇到稍微变形就不会那这篇文章里关于状态设计和转移优化的思路同样对你有用。我刷完这一整套初阶题大概花了三周时间每天投入两到三小时。中间踩了不少坑也总结出了一些题解里不会写的经验。下面我把整个练习过程拆开来讲从思路设计到具体实现再到踩坑记录尽量做到你看了就能直接上手刷。2. 初阶DP题单的整体设计与刷题思路2.1 为什么选择按题型分类刷而不是按难度顺序刷洛谷的题单有两种组织方式一种是按难度评级从低到高排列另一种是按算法类型分组。我强烈建议初阶DP练习按题型分类来刷而不是盲目按难度排序。原因很简单DP的核心难点在于状态设计和转移方程的推导而同一类题型的思维模式是高度相似的。你连续做五道背包问题做到第三道的时候基本就能条件反射地想到这个容量维度要不要压掉这个物品是01还是完全。但如果你今天做一道背包、明天做一道区间DP、后天做一道树形DP每次都要重新切换思维模式学习效率会大打折扣。具体来说我建议的刷题顺序是这样的线性DP约8到10题这是最基础的DP形式状态通常是一维或二维的转移方向单一。典型问题包括最长上升子序列、最大子段和、数字三角形等。背包问题约6到8题01背包、完全背包、多重背包以及它们的变体。背包问题是DP入门的分水岭理解了背包基本就理解了DP的核心思想。区间DP约4到5题状态定义在区间上通常需要枚举分割点。入门题以石子合并、括号匹配为代表。树形DP约3到4题在树结构上进行DP通常需要递归遍历。入门题以没有上司的舞会、树的直径为代表。递推与计数DP约4到5题包括简单的方案计数、Catalan数相关的递推等。每个类型内部先做最裸的模板题再做一到两道变形题。模板题的目的是让你把代码框架刻进肌肉记忆里变形题的目的是让你理解状态设计的灵活性。2.2 每道题的练习流程应该怎么走很多人刷题的习惯是看题、想五分钟、不会、看题解、抄代码、下一题。这个流程的问题在于你跳过了最重要的环节——独立思考状态设计的过程。我自己的流程是这样的读题后先判断题型这道题求的是什么最优值、方案数、还是可行性数据范围大概暗示了什么复杂度尝试定义状态用一两句话写出dp[i]表示什么。这一步最关键状态定义对了转移方程往往水到渠成。推导转移方程从最后一步入手思考dp[i]可以从哪些更小的状态转移过来。手动模拟小样例用纸笔把dp数组的前几项算出来验证转移方程是否正确。写代码实现注意边界条件、初始化、循环顺序。如果卡住了超过20分钟看题解的思路部分但不要看代码自己实现。做完后回顾这道题的状态设计有什么特点如果数据范围变了我的做法还能用吗这个流程看起来慢但坚持下来你独立解题的能力会提升得非常快。我前两周基本每天只能做两三道题但到了第三周很多题看完就能直接写出转移方程。2.3 初阶DP的核心能力目标刷完这一套初阶题你应该具备以下能力看到一道题能在五分钟内判断它是否可以用DP解决能独立设计出一维和二维的状态定义熟练掌握01背包和完全背包的一维滚动数组写法理解区间DP的枚举顺序为什么必须是区间长度从小到大能写出简单的树形DP递归框架知道什么时候需要开long long什么时候会爆int这些能力不是靠看题解看出来的是靠一道一道题手推出来的。下面我进入具体的核心细节解析。3. 核心细节解析与实操要点3.1 状态设计的本质用什么维度描述子问题状态设计是DP的灵魂。很多初学者觉得DP难难就难在不知道怎么定义状态。我总结了一个实用的思考框架状态 问题的规模 附加约束。举个例子。最长上升子序列问题给你一个数组求最长的严格递增子序列长度。这里的问题规模是以第i个元素结尾附加约束没有所以状态就是dp[i] 以第i个元素结尾的最长上升子序列长度。再比如01背包有n个物品容量为V的背包每个物品有重量w和价值v求最大价值。这里的问题规模是考虑前i个物品附加约束是当前背包容量为j所以状态是dp[i][j] 前i个物品在容量j下的最大价值。这个框架几乎适用于所有初阶DP题。你拿到一道题先问自己两个问题子问题的规模用什么描述除了规模之外还有什么限制条件需要记录把这两个问题的答案组合起来状态就出来了。注意状态定义不是唯一的。同一道题可以有不同的状态定义方式只要转移方程能正确推导并且复杂度可接受就行。但初学者建议先用最直观的定义方式熟练之后再尝试优化。3.2 转移方程的推导从最后一步倒着想状态定义好之后下一步是推导转移方程。我用的方法叫最后一步法假设你已经知道了所有更小规模的子问题的答案现在考虑当前规模的问题它的最后一步做了什么决策以数字三角形为例。给你一个三角形排列的数字从顶部走到底部每次只能走到下一行相邻的位置求路径上数字之和的最大值。状态定义dp[i][j] 从顶部走到第i行第j列的最大路径和。最后一步是什么要么是从左上角(i-1, j-1)走下来的要么是从右上角(i-1, j)走下来的。所以转移方程就是dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]你看最后一步法把转移方程的推导变得非常机械化。你只需要想清楚到达当前状态的前一个状态可能是什么转移方程自然就出来了。3.3 背包问题的初始化细节最容易翻车的地方背包问题是初阶DP里最容易在初始化上翻车的地方。我见过太多人转移方程写对了但初始化搞错导致答案不对。先回顾一下01背包的一维写法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]); } }这里有两个关键细节第一内层循环必须从大到小枚举。为什么因为一维数组是滚动使用的dp[j]的值依赖于上一轮即前i-1个物品的dp[j-w[i]]。如果从小到大枚举dp[j-w[i]]可能已经在当前轮被更新过了那就变成了完全背包每个物品可以用无限次而不是01背包。这个细节几乎每本算法书都会讲但真正写代码的时候还是容易搞混。第二初始化取决于问题问的是什么。如果问题要求恰好装满背包的最大价值那么dp[0] 0其余dp[j] -infinity。如果问题不要求装满只是求最大价值那么所有dp[j] 0。这个区别的本质在于dp数组的初始值代表了什么状态是合法的。我个人的记忆方法是恰好装满时只有容量为0的背包在不装任何东西时是合法的其他容量在没有物品时都是不可达的所以设为负无穷。不要求装满时任何容量的背包在不装任何东西时价值都是0所以全部设为0。3.4 区间DP的枚举顺序为什么不能随便写区间DP的典型框架是这样的for (int len 2; len n; len) { // 枚举区间长度 for (int i 1; i len - 1 n; i) { // 枚举区间起点 int j i len - 1; // 区间终点 for (int k i; k j; k) { // 枚举分割点 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost); } } }这个三层循环的顺序不能随便改。最外层必须是区间长度因为区间DP的转移依赖于比当前区间更短的子区间。如果你先枚举起点再枚举终点那么在计算dp[i][j]的时候dp[i][k]和dp[k1][j]可能还没有被计算出来。这个道理和线性DP中从前往后递推是一样的——你必须保证在计算当前状态时所有它依赖的状态都已经计算完毕。区间DP的依赖关系是短区间依赖更短的区间所以按长度从小到大枚举是唯一正确的顺序。实操心得写区间DP的时候我习惯先把dp[i][i]的初值全部设好通常是0或者题目给定的单元素值然后从len2开始枚举。这样不容易出错。4. 实操过程与核心环节实现4.1 线性DP实战最长上升子序列的三种写法最长上升子序列是线性DP的经典入门题。题目描述很简单给定一个长度为n的数组求最长严格递增子序列的长度。写法一O(n²)的朴素DP状态定义dp[i] 以第i个元素结尾的最长上升子序列长度。转移方程dp[i] max(dp[j]) 1其中j i且a[j] a[i]。int lis(vectorint a) { int n a.size(); vectorint dp(n, 1); int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }这个写法的时间复杂度是O(n²)适用于n不超过5000的情况。初阶题的数据范围通常在这个量级。写法二O(n log n)的贪心二分维护一个数组tailstails[i]表示长度为i1的上升子序列的最小结尾元素。遍历原数组对于每个元素用二分查找找到tails中第一个大于等于它的位置替换掉。int lis_fast(vectorint a) { vectorint tails; for (int x : a) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) tails.push_back(x); else *it x; } return tails.size(); }这个写法严格来说不算DP但它的思想来源于DP的优化。初阶题单里通常只要求掌握O(n²)的写法但了解O(n log n)的写法对后续进阶有帮助。写法三树状数组优化当元素值域较大时可以用树状数组维护前缀最大值把转移优化到O(log n)。这个属于进阶内容初阶阶段了解即可。我在刷这部分题目时的体会是先把O(n²)的写法写熟做到闭着眼睛都能写出来。然后再去理解O(n log n)的优化思路。不要一上来就追求最优解法那样反而容易两头都学不扎实。4.2 背包问题实战从二维到一维的滚动数组优化背包问题是初阶DP的核心。我以01背包为例完整走一遍从二维到一维的优化过程。二维写法状态定义dp[i][j] 前i个物品容量为j的背包能获得的最大价值。转移方程不选第i个物品dp[i][j] dp[i-1][j]选第i个物品前提是j w[i]dp[i][j] dp[i-1][j-w[i]] v[i]for (int i 1; i n; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i]); } } }一维写法滚动数组观察二维写法可以发现dp[i][j]只依赖于dp[i-1][...]也就是说第i行的值只依赖于第i-1行。所以我们可以把第一维压掉只保留第二维。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]); } }注意内层循环从V递减到w[i]。为什么递减因为在二维写法中dp[i][j]依赖的是dp[i-1][j-w[i]]也就是上一行的值。一维数组中如果我们从大到小枚举j那么dp[j-w[i]]在此时还没有被第i轮更新过它保存的仍然是上一轮的值等价于dp[i-1][j-w[i]]。如果从小到大枚举dp[j-w[i]]可能已经被第i轮更新了那就变成了完全背包。完全背包的一维写法完全背包中每个物品可以选无限次转移方程变为dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])。注意第二项是dp[i]而不是dp[i-1]因为可以重复选。对应到一维写法内层循环从小到大枚举即可for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j-w[i]] v[i]); } }实操心得01背包和完全背包的代码只差一个循环方向但含义完全不同。我建议在写的时候嘴里默念01从大到小完全从小到大形成条件反射。4.3 区间DP实战石子合并的完整推导石子合并是区间DP最经典的入门题。题目描述有n堆石子排成一排每次可以将相邻的两堆合并成一堆合并的代价是两堆石子数量之和。求将所有石子合并成一堆的最小总代价。状态定义dp[i][j] 将第i堆到第j堆石子合并成一堆的最小代价。转移方程考虑最后一次合并一定是将区间[i, j]分成两部分[i, k]和[k1, j]分别合并后再合并这两堆。所以dp[i][j] min(dp[i][k] dp[k1][j]) sum(i, j)其中k从i到j-1。其中sum(i, j)是第i堆到第j堆的石子总数可以用前缀和预处理。完整代码int stoneMerge(vectorint stones) { int n stones.size(); vectorint prefix(n 1, 0); for (int i 0; i n; i) { prefix[i1] prefix[i] stones[i]; } vectorvectorint dp(n, vectorint(n, 0)); for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j]); } dp[i][j] prefix[j1] - prefix[i]; } } return dp[0][n-1]; }参数计算过程假设有4堆石子数量分别为1、3、5、2。前缀和prefix [0, 1, 4, 9, 11]。len2时dp[0][1] dp[0][0] dp[1][1] (13) 0 0 4 4dp[1][2] 0 0 (35) 8dp[2][3] 0 0 (52) 7len3时dp[0][2] min(dp[0][0]dp[1][2], dp[0][1]dp[2][2]) (135) min(08, 40) 9 4 9 13dp[1][3] min(dp[1][1]dp[2][3], dp[1][2]dp[3][3]) (352) min(07, 80) 10 7 10 17len4时dp[0][3] min(dp[0][0]dp[1][3], dp[0][1]dp[2][3], dp[0][2]dp[3][3]) (1352) min(017, 47, 130) 11 11 11 22最终答案是22。这个手动计算的过程非常重要。我建议每道区间DP题都至少手动模拟一遍小样例这样你能真正理解dp数组的含义和转移的过程。4.4 树形DP实战没有上司的舞会树形DP的入门经典题是没有上司的舞会。题目描述一棵树上有n个节点每个节点有一个快乐值。如果选择了某个节点就不能选择它的直接父节点。求能获得的最大快乐值总和。状态定义dp[u][0] 不选节点u时以u为根的子树能获得的最大快乐值dp[u][1] 选节点u时以u为根的子树能获得的最大快乐值转移方程如果选了u那么u的所有子节点都不能选dp[u][1] happy[u] sum(dp[v][0])其中v是u的子节点如果不选u那么u的每个子节点可以选也可以不选dp[u][0] sum(max(dp[v][0], dp[v][1]))代码实现递归写法void dfs(int u, vectorvectorint children, vectorint happy, vectorvectorint dp) { dp[u][1] happy[u]; dp[u][0] 0; for (int v : children[u]) { dfs(v, children, happy, dp); dp[u][1] dp[v][0]; dp[u][0] max(dp[v][0], dp[v][1]); } }树形DP的关键在于递归的顺序先处理所有子节点再处理当前节点。这和后序遍历的顺序是一致的。写树形DP的时候我习惯用递归实现因为树的递归结构天然适合后序遍历。如果树很深比如链状树递归可能导致栈溢出这时候需要改成迭代写法或者手动开栈。注意树形DP的建图方式很重要。如果是无根树需要任选一个节点作为根然后在DFS时记录父节点避免走回头路。如果题目给的就是有根树比如给出了父子关系直接建子节点列表即可。5. 常见问题与排查技巧实录5.1 答案不对时怎么排查DP题的调试比普通题要难因为状态转移是层层依赖的一个地方的错误会传播到最终答案。我总结了一套排查流程第一步检查初始化。这是最常见的错误来源。dp数组的初值是否符合题意边界条件dp[0]、dp[i][0]等是否设置正确背包问题中恰好装满和不要求装满的初始化区别是否搞清楚了第二步检查循环顺序。线性DP的循环方向是否正确背包问题的内层循环方向是否正确区间DP是否按区间长度枚举这些顺序错误往往不会导致程序崩溃但会得到错误答案。第三步检查转移方程。把转移方程重新推导一遍确认没有遗漏情况。特别注意边界情况比如i0或j0时转移方程是否还成立。第四步手动模拟小样例。用纸笔把dp数组的每个值算出来和程序输出的dp数组对比。这是最有效的排查方法能直接定位到出错的步骤。第五步检查数据范围。是否会爆int是否需要开long long数组大小是否足够下面这张表是我整理的常见错误速查表错误现象可能原因排查方法答案偏小初始化不够大求最小值时检查dp数组初值是否为正无穷答案偏大初始化不够小求最大值时检查dp数组初值是否为负无穷或0背包答案错误内层循环方向搞反01背包从大到小完全背包从小到大区间DP答案错误枚举顺序不对确保最外层是区间长度树形DP答案错误递归顺序不对确保先处理子节点再处理当前节点部分测试点WA边界条件未处理检查n1、V0等特殊情况全部TLE复杂度太高检查是否可以用滚动数组或前缀和优化5.2 复杂度分析与优化时机初阶DP题的数据范围通常会给你足够的提示。我整理了一个经验对照表数据范围可接受的复杂度常见DP类型n ≤ 20O(2^n)状压DPn ≤ 100O(n³)区间DPn ≤ 500O(n³)区间DP常数小n ≤ 5000O(n²)线性DP、背包n ≤ 10^5O(n log n)线性DP优化n ≤ 10^6O(n)线性DP看到n ≤ 5000基本可以确定是O(n²)的DP。看到n ≤ 100大概率是O(n³)的区间DP。这个判断能帮你在读题阶段就锁定解题方向。优化时机的判断如果朴素DP的复杂度刚好卡在时限边缘可以尝试常数优化比如用register变量、减少取模次数。如果复杂度差了一个量级就需要考虑算法层面的优化比如单调队列优化、前缀和优化、滚动数组等。5.3 那些题解不会告诉你的踩坑经验坑一long long不是万能的。有些题目中间结果会超过long long的范围需要用高精度或者取模。初阶题里比较少见但一旦遇到要养成看数据范围估算最大值的习惯。比如n1000每个数最大10^9那么总和最大10^12在long long范围内约9×10^18。但如果n10^5每个数最大10^9总和就是10^14仍然安全。再大就要小心了。坑二memset不能把数组设成1。memset是按字节赋值的memset(dp, 1, sizeof(dp))会把每个int设成0x01010101而不是1。正确的做法是用fill或者循环赋值。这个坑我在初学阶段踩过好几次。坑三二维数组的维度顺序影响缓存命中率。dp[i][j]和dp[j][i]在逻辑上可能等价但在内存访问模式上差别很大。一般来说把变化更快的维度放在后面即dp[较小维度][较大维度]缓存命中率更高。这个在数据量大的时候能带来几倍的常数差异。坑四递归树形DP可能爆栈。如果树是一条链递归深度等于节点数。n10^5时递归会爆栈。解决办法是手动开大栈空间或者改成迭代写法用栈模拟后序遍历。坑五多组数据要清空数组。有些题目有多组测试数据如果忘记清空dp数组上一组的数据会污染下一组的结果。我习惯在每组数据开始前用fill把dp数组重置。5.4 如何判断一道题是否该用DP这是初学者最常问的问题。我的判断标准有三条第一问题具有最优子结构。也就是说大问题的最优解可以由小问题的最优解推导出来。比如最短路径问题从A到C的最短路径一定经过某个中间点B且A到B和B到C的路径也是最短的。第二子问题有重叠。如果子问题之间没有重叠那用分治就好了不需要DP。DP的本质就是用空间换时间把重复计算的子问题结果存下来。第三问题要求的是最优值、方案数或可行性。这三类问题最容易用DP建模。如果问题要求的是具体方案比如输出路径DP也可以做但需要额外记录转移来源。三条都满足基本可以确定用DP。如果只满足前两条可能是贪心或者分治。如果只满足第三条可能是搜索或者数学方法。6. 刷完初阶题之后的路该怎么走刷完这一套初阶DP题你应该已经建立了对DP的基本感觉。接下来有几个方向可以继续深入。第一个方向是提高DP的复杂度优化能力。初阶题的数据范围通常允许O(n²)甚至O(n³)的复杂度但进阶题往往需要O(n log n)甚至O(n)。你需要学习单调队列优化、斜率优化、四边形不等式等技巧。这些内容在洛谷的进阶题单里都有对应的训练。第二个方向是扩展DP的模型类型。初阶题主要覆盖线性DP、背包、区间DP和树形DP。进阶阶段还有状压DP、数位DP、概率DP、博弈DP等。每种模型都有自己独特的状态设计思路。第三个方向是结合其他算法。很多进阶题不是纯DP而是DP和贪心、二分、图论等算法的结合。比如二分答案DP判定、DP最短路等。我个人的建议是不要急着刷进阶题。先把初阶题反复刷两到三遍做到每道题都能在15分钟内独立写出正确代码。这个过程中你会逐渐形成对DP的直觉——看到一道题状态定义和转移方程会自然地浮现在脑海里。这种直觉才是刷题最大的收获。最后分享一个我一直在用的练习方法每做完一道DP题用一句话总结这道题的状态定义和转移方程记在一个本子上。过一周再回来看这些总结尝试只看总结就还原出完整代码。如果能做到说明你是真的理解了如果做不到说明当时只是抄了题解需要重新做一遍。这个方法看起来很笨但效果非常好。我坚持了两个月记了大概八十多道题的总结后来遇到新题的时候很多状态设计的思路都能从之前的总结里找到影子。DP说到底就是模式识别你见过的模式越多解题就越快。