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 最长上升子序列（LIS）：O(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。它的做法是维护一个数组d，d[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[i+1][j], dp[i+1][j+1]) + 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]已经合并成一堆，右边[k+1,r]已经合并成一堆，最后这两堆再合并一次，花费是sum[l][r]。所以dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum[l][r])，对所有k从l到r-1取最小。

区间DP的遍历顺序特别讲究。你不能直接按l从1到n、r从l到n去填，因为计算长区间的时候会用到短的区间，但是如果你按起点枚举，可能短的右区间还没算出来。标准做法是先枚举区间长度len，从2到n，再枚举左端点l，右端点r = l+len-1，最后枚举分割点k。这个顺序保证你算长区间的时候，所有子区间长度都小于当前长度，已经被算过了。空间复杂度O(n^2)，时间复杂度O(n^3)，n几百以内没问题，再大就要想四边形不等式优化，这是竞赛进阶内容，不展开。

P1880还有一个环形变体，就是把石子堆摆成一个环，首尾也能合并。解法是复制一遍数组，把环形转化成链形，枚举长度为n的窗口求最值。这个“复制翻倍破环成链”的技巧非常常用，洛谷后面很多环状DP（比如能量项链P1063）也是这么干的。

4.2 背包DP：01背包为什么要倒序遍历，完全背包为什么正序

背包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|(1<<u)][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题清单，从入门到进阶，每一道题都对应一个独立模型，题与题之间不重复、有递进关系。

6.2 刷题顺序与每道题的“验收标准”

刷题不是做完就完，每道题要有一个验收标准。比如P1216，指标是你能在5分钟内写完且一次AC；P1020要求你写出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题的过程中，有几类错误出现频率极高，我把它们整理成了一个对照表，你可以保存下来当排查手册用。

7.3 事不过三：DP的“过题策略”

最后分享一个刷题技巧。现在的在线评测平台，比如洛谷，都有“提交记录”和“题解区”。我的建议是，一道DP题你提交超过3次还不过，就停下来。不是说你写不出来，而是说“硬碰硬”的效率太低。停下来做的事情是：去看题解区的高赞题解，重点看人家的“状态定义和转移方程”，然后完全关闭题解，自己重新写一遍代码。很多时候，你差的不是代码能力，而是“没想到状态可以这么定义”这个灵感，而这个灵感靠死磕是磕不出来的。

用这个方法，我把洛谷的DP题单刷完一轮之后，再回头看那些以前觉得“看不懂”的题，基本都能在10分钟内理出思路。这就是模型化的力量——当你的脑子里有足够多的状态定义模板，新题在你眼里就不再是“全新的”，而是“某个旧模板的变体”。

我个人在实际写代码的过程中还有一个习惯：每道DP题AC之后，我会在题解区看一眼别人有没有更巧妙的状态定义。这个动作看着不起眼，但它能帮你积累“一题多解”的视野。很多时候，一个更优雅的状态定义，比一个AC的写法更能提升你的DP水平。