企业官网建设流程全解析

动态规划这个系列写到第11篇，能一路跟下来的朋友，多半已经在背包、区间DP、状态机这些模型里打过转，也踩过不少坑。老实讲，很多初学者走到现在的最大困惑不是“什么是DP”，而是“看题解全会，关上屏幕全废”，尤其是遇到线性dp、状态压缩这一类场景时，总觉得别人的状态定义像变魔术。这篇我不打算引入新模型，而是想把动态规划的模型原理、线性dp的常见套路、洛谷动态规划题单的实战选择，以及车辆动态规划问题这类工程应用放在一起做一次集中串讲。

先说明这篇适合谁：正在学DP但还不会独立设计状态的人；刷题到了瓶颈期想系统复盘的人；上过算法课但不知道DP怎么落到实际场景的同学。只要中了其中一条，这篇应该能帮你把线头理顺。我尽量用讲人话的方式，把从“看懂”到“会写”之间那个坎拆开，逐步跨过去。

1. 动态规划到底在干什么：模型原理与核心思路

1.1 抛开术语，DP其实是一种“聪明的枚举”

很多人一学DP就被“最优子结构”“无后效性”“重叠子问题”这些词吓住，其实是没找到合适的参照物。我们把DP拆开看，它本质上还是在枚举所有可能方案，只不过它把计算结果存了下来，让相同子问题只算一遍。

举个生活化的例子。你想从公司回家，路上要经过几个路口，每条路都有不同时间。最笨的办法是把所有路线都走一遍记录时间，这是暴力搜索。聪明一点的办法是，先算出“到第一个路口的最短时间”，再算“到第二个路口的最短时间”，每次都站在前一个路口的最短路基础上，只用考虑下一段怎么走。这就是DP：用一张表记录部分答案，用已经算出来的答案推出新答案，避免重复劳动。

所以在正式做DP题之前，我会先在草稿纸上问自己三个问题：这个问题能拆成更小的子问题吗？子问题的答案能不能被重复使用？后面的决策是不是只依赖前面的结果，而不依赖前面具体怎么走出来的？如果都是肯定的，这就是一道DP题。这三个问题的答案，其实就是最优子结构和无后效性，但与其背术语，不如把它们当成“能不能用DP”的思维检查表。

1.2 状态定义与转移方程的“三步法”

给一道DP题，我反复强调的套路只有三步，但每一步都值得琢磨：

第一步，定义状态。dp[i] 表示什么？是前 i 个物品能装的最大价值，还是走到第 i 个位置的最少花费？状态定义必须精确到“变量含义”和“值含义”两层，缺一不可。很多人后面转移写不出来，几乎都是状态含糊导致的。

第二步，写转移方程。当前状态 dp[i] 和哪些更小的状态有关？把所有可能来源列出，取 max 或 min，或者做加法、做计数，看题目要求什么。

第三步，确定初始化与答案。dp[0]、dp[1] 这种起点值是多少？答案取 dp[n] 还是整个dp数组的最大值？

这三步没有固定顺序，有时候先想答案的位置，反过来更容易定状态。但无论顺序怎么换，核心都是“状态定义”这一个支点，支点稳了，转移就是水到渠成的事。

我再补一个实际操作中的心得：状态定义如果有犹豫，就把定义的描述写成一整句中文，比如“dp[i][j] 表示前 i 个物品中选出若干个，总重量正好为 j 时能获得的最大价值”——写得出来，才算真的想清楚了。

1.3 初始化与边界：出错的头号来源

刷DP题，最让我崩溃的不是转移方程写错，而是初始化写错。因为方程错了往往一眼能看出来，初始化错了可能跑样例都看不出来，一提交就全盘皆输。

常见的坑有这么几类。一类是“不知道该初始化成0还是无穷大”。如果是求最小值，无效状态一般要初始化成 INF，保证它不会被选到；如果是求最大值，则初始化成 -INF，或者说一个很小的负数。第二类是下标边界没处理好，比如 dp[0] 表示什么、循环从1开始还是从0开始，不同写法会直接改变结果。第三类是“无解”状态混进了答案，比如路径计数里有些点根本走不到，但如果你不把对应dp值设置成0，它就可能被误当成一条可行路径。

我自己常用一个小技巧来排查边界：把样例缩到最小，比如数组长度1、目标值1这种情况，手推一遍整个过程，再对照代码跑一遍。边界问题在极小规模数据下会暴露得特别明显，比盲目调试有效得多。

2. 线性DP：最常用也最练基本功的DP类型

2.1 什么才叫线性DP

线性DP，准确说是指状态转移发生在一条有序的链上，从小到大或者从前往后推进。它不是指“数据结构是数组”，而是强调转移的拓扑关系是一条线。一维数组上的最大子段和、最长上升子序列、最长公共子序列，这些都是线性DP的经典代表。

为什么强调线性？因为它是理解DP递推顺序的最佳切入口。在线性结构上，你很容易看清“当前状态依赖哪些前置状态”，也很容易理解为什么循环必须从小到大跑。一旦这种顺序感建立起来，后面学区间DP、树形DP时，你就能更快抓住“哪些状态先算出来”这个命门，而不会被复杂的结构带偏。

另外要说明的是，二维的棋盘路径问题也常被归入线性DP一类，因为虽然状态有两个维度，但转移方向依然是线性的。所以别被“线性”两个字误导，它更核心的思想是“有明确递推方向的DP”。

2.2 最大子段和：一个模型打通贪心与DP

我先讲一个最简单的入门例子：给一个数组，求连续子数组的最大和。最暴力是枚举左右端点，O(n^2)；如果先做前缀和，可以优化到 O(n^2)；但如果用DP，一行转移就能做到 O(n)。

定义 dp[i] 表示“以第 i 个元素结尾的连续子数组的最大和”，那么写得出转移方程：

dp[i] = max(dp[i-1] + a[i], a[i])

这个式子怎么理解？以 i 结尾的子数组，要么延续以 i-1 结尾的那段最优子数组，要么从 a[i] 单独开始。两者取大即可。最后答案就是所有 dp[i] 中的最大值。

注意，这个DP最大的“反直觉”在于：每次求的是“以当前元素结尾”的值，而不是“前 i 个元素里的最大子段和”。这两个定义差一个字，转移完全不同。如果定义成后者，转移反而不好写。所以以后再遇到“定义状态时总觉得差点意思”的情况，试试把目光聚焦在“以…结尾/包含最后一个元素”这个角度上，往往一下就通了。

在实际编码中，因为 dp[i] 只依赖 dp[i-1]，还可以用一个变量滚动记录，不需要开数组：

cur = max(cur + a[i], a[i]) ans = max(ans, cur)

这也是在线性DP里最常见的空间优化雏形。

2.3 最长上升子序列：从O(n^2)到O(n log n)

最长上升子序列（LIS）是线性DP里我个人觉得最值得反复琢磨的题目。常规做法很直观，定义 dp[i] 表示以第 i 个元素结尾的最长上升子序列长度，那么：

dp[i] = max( j<i 且 a[j] < a[i]，取 dp[j] + 1 )

翻译成代码就是两层循环，第一层枚举 i，第二层枚举所有 j < i，满足数值小于当前值就尝试更新。复杂度 O(n^2)，n 不超过几千还能跑，上万就开始吃力了。

优化版本需要换一个视角。我们可以维护一个数组 low[ len ]，表示长度为 len 的上升子序列的末尾元素最小值。遍历每个 a[i] 时，在 low 数组里做二分查找，找到第一个大于等于 a[i] 的位置，替换它。如果找不到，说明可以扩展长度，low 长度加一。这个技巧的妙处在于：low 数组单调递增，二分查找让整体复杂度变成 O(n log n)。

很多人第一次看到这个优化会觉得它是贪心，不是DP。实际上它依然是DP思想的延伸——我们在用二分维护“当前最优末尾值”，这正是DP里“保留最优子结构”的另一种表现形式。建议自己手动推一遍 a = [3, 1, 4, 1, 5] 的例子，看看 low 数组的变化过程，理解深度会比直接背代码好得多。

2.4 最长公共子序列：二维DP的敲门砖

最长公共子序列（LCS）是二维线性DP的典型。给定两个字符串 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] )

这个转移逻辑是按最后一个字符是否匹配来分类的，非常经典。相等时直接接在“两边都少一个字符”的结果后面；不相等时，这个字符至少有一边用不到，所以取两边各退一步的较大值。

要真正掌握这个模型，建议画一张二维表，把两个字符串分别标在行和列上，手推一遍填充过程。你会发现每个格子的值都来自左上、左、上三个方向，整个表的填充顺序按行从左到右、从上到下进行。这种“肉眼可见”的递推顺序，比任何解释都更有说服力。

LCS 还有一个经典变体是打印出具体的最长公共子序列，做法是DP完以后从 dp[n][m] 开始回溯。如果 dp[i][j] 来自 dp[i-1][j-1] 且字符相等，就记录这个字符；否则往较大的方向移动。这个回溯过程，也是面试里喜欢追问的细节。

2.5 线性DP的状态设计规律总结

学到这里，可以把线性DP的状态定义规律汇总一下，我用表格列几个最常见的模板，方便当工具书查阅。

这些模板本质上都可以分成两类：一类是“以 i 结尾”型，答案需要扫描整个dp数组取最值；另一类是“前 i 个”型，答案直接取 dp[n] 或 dp[n][m]。拿到题目先判断该用哪种视角，状态定义基本就定了一半。

还有一个我反复说过的经验：不要背模板，要理解“这个状态为什么长这样”。每道新题都尝试从这两个视角去想，坚持五十题之后，你会发现自己对状态的定义敏感度会明显提升。

3. 洛谷题单实战拆解：从会看题到会AC

3.1 题单怎么选、怎么安排顺序

洛谷的动态规划题单很丰富，从入门到提高都有。我的建议是别一股脑刷，先按题型和难度分层：第一层做“数字三角形”“过河卒”这种纯递推/记忆化搜索的题，目标是理解DP的填表过程；第二层做LIS、LCS这类第一、二维线性DP，目标是熟练状态定义；第三层才做背包变体和区间DP，目标是掌握更复杂的转移。

具体刷题时，我习惯每道题只看题目，不看题解，先自己憋30分钟到1小时。憋不出来再打开题解看状态定义那三行，然后合上题解自己写代码。这个方法看起来笨，但实际效率远高于“边看边抄”。因为看题解最大的损失不是不会做，而是没有经历“从卡住到想通”的过程，而这个过程恰恰是训练DP思维的核心。

另外一个安排上的细节：每道AC的题，我会在题号旁边记下“模型关键词”。比如P1216记“递推方向+滚动数组”，P1434记“记忆化搜索”。为什么要做这个标记？因为DP题目千变万化，但模型就那几十种，等刷到100题时翻回来看，你会发现自己其实一直在跟少数几个模板打交道。这个复盘动作，比多刷20道新题的价值更大。

3.2 P1216 数字三角形：递推方向的选择

洛谷P1216是一道极其适合入门数字三角形的题目。题目是给一个由数字组成的三角形，从顶部出发，每次可以走到正下方或右下方，问路径上数字和的最大值。

最自然的想法是从上往下递推：dp[i][j] 表示从顶点走到第 i 行第 j 个位置的最大和，转移就两个来源，上方和左上方。但这么做有一个细节很烦——每一行的左右边界都要单独判断，防止越界访问数组。

另一种常见做法是自底向上递推：从三角形的最后一行开始往上走，每个位置选择下一行中较大的那个数加上自己。好处是边界处理简单，最后一行的初始值就是三角形本身的数字，一路推到最顶部就出答案。状态转移可以写成：

dp[i][j] = max( dp[i+1][j], dp[i+1][j+1] ) + triangle[i][j]

自底向上的写法省去了很多边界判断，代码量更少，也更容易写对。我个人在带新手做这道题时，都会让他们两种方向各写一遍，亲身体会为什么工程上喜欢选递推方向麻烦更小的那一边。这个“选方向”的意识，在做区间DP时同样重要，因为它直接影响循环的写法与边界处理的难度。

3.3 P1434 滑雪：记忆化搜索就是DP的递归形式

洛谷P1434“滑雪”是另一个经典入门题，在一个二维矩阵里找一条最长下降路径，可以从任意位置出发，每次滑向高度更低的相邻格。

这道题如果直接DP，会发现一个问题：状态之间的依赖顺序不明显，因为你不知道哪个格子先被算更好。从低处往高处推，还是反过来，都容易卡住。这时候有一个非常好用的工具：记忆化搜索。

记忆化搜索本质上就是递归版的DP，用深度优先搜索枚举转移，同时开一个 memo 数组缓存已经算过的结果。比如定义 dfs(i,j) 表示从 (i,j) 出发能滑到的最长路径长度，那么：

dfs(i,j) = 1 + max( dfs(ni,nj)，其中 (ni,nj) 是高度更低的相邻格子 )

每次递归时先查 memo 数组，算过就直接返回；没算过就四个方向试探，最后把结果存进 memo。由于每个格子只会被完整计算一次，总体复杂度也是 O(n*m)。

这道题给我的最大启发是：DP的递推顺序不是一定要显式地从小到大，只要保证“在计算某个状态前，它依赖的状态已经算好”，可以采用任何实现方式。递归+记忆化很多时候能免去排序、免去分析法，是降低思维负担的有效手段。当然，递归要注意系统栈深度，一般二维矩阵几百乘几百是安全的，如果数据范围特别大，还是要改写成迭代递推。

3.4 P1002 过河卒：路径计数里的障碍处理

过河卒这道题表面上是棋盘路径问题，其实可以归入线性DP。题目说有一个卒从 (0,0) 出发，只能向右或向下走，目标在 (n,m)，棋盘上有一只马的“日”字控制点不能经过，问有多少条路径。

没有障碍时的状态转移非常简单：dp[i][j] = dp[i-1][j] + dp[i][j+?]，其实就是“到当前位置的路径数等于从左边来和从上面来的路径数之和”。加了马的控制点之后，只要在转移前判断一下当前位置是否被马控制，如果控制，则直接跳过。

这道题让我想特别提醒两个细节。第一个是注意马的攻击范围不只是它站的那个点，还包括马走“日”字能到达的八个点，全部都要标记。第二个是数据范围：路径数很容易超过int的表示能力，必须使用 long long，否则AC近在眼前却白白WA一次。我在初次提交这道题时就被第二个坑坑过，从此所有路径计数题一律默认用 long long 起步，排查溢出远比事后改类型更省心。

还有一个容易忽略的点是边界处理。当 i-1 或 j-1 越界时，那个方向的路径数按0算。有的写法会把dp数组开大一圈，让下标从1开始，这样就能省掉很多 if 判断。这类“开大数组避免越界”的思路，在二维DP里非常实用，我自己几乎每道棋盘类DP都会用上。

3.5 实战心得：一道题从卡住到AC的完整心流

我在带学弟学妹刷题单时，经常被问到：“为什么我看完题解就理解了，但下次遇到还是不会？”这个问题的本质是，你跳过了从“问题”到“状态定义”的那段思考过程。而这段过程恰恰是DP能力真正的分水岭。

以数字三角形为例，我遇到新手的完整心流通常是：先尝试枚举所有路径——发现数量爆炸；接着想从上往下记录每一步的最大和——发现每一步的最优可以基于上一步最优得出；然后用数组存每一行的值——发现要处理边界；最后AC。这个过程看起来绕，但它完整经历了“暴力→优化→状态抽象→边界处理”四个阶段。只看AC代码，你永远体会不到这个抽象过程。

所以我建议，做DP题时给自己立一个规矩：写代码前，先在草稿纸上把状态定义和转移方程写出来。哪怕写得不对，这个动作本身就在倒逼你思考。坚持一段时间后，你会发现花在“想”上的时间越来越多，花在“改”上的时间越来越少。

4. 车辆动态规划问题：从OJ题到工程现场

4.1 这类问题长什么样

聊完算法题，我们把视野拉到工程应用上。动态规划在车辆领域有一个很典型的组合优化问题族：车辆路径问题（Vehicle Routing Problem，VRP）、车辆调度、充电规划、AGV搬运路径等等。这些问题的共同点是：需要在一组离散的决策点上，为车辆选出一条或多条路径，使得总成本最小、总时间最少、或者覆盖客户最多。

拿一个简单的场景举例。假设有一个配送站，三辆小货车要往十五个客户点送货，每辆车容量不同，客户有时间窗要求，路线怎么安排才能总里程最短？这类问题的核心难点在于，配送顺序的可行组合数量是阶乘级别的，暴力枚举根本不可能算完，而DP恰好能在“枚举所有顺序”这件事上，用“集合+最后位置”这一招压缩复杂度。

当然，实际工程里的车辆问题往往比算法题复杂很多，有装载约束、时间窗、司机休息规则、实时路况等因素，不能直接套用教科书公式。但DP依然是很多精确算法的底层骨架，也经常作为启发式算法里的局部搜索算子，所以把基础模型搞懂非常值得。

4.2 从旅行商问题到状态压缩DP

学习车辆路径问题，最好的切入点是从旅行商问题（TSP）开始。TSP是VRP的简化版：一个销售员要拜访 n 个城市，每个城市必须去且只去一次，最后回到起点，求最短回路。

对TSP做DP，经典做法是状态压缩。定义 dp[S][i] 表示“当前已经访问过的城市集合为 S，最后停在第 i 个城市时，走过的总路径长度最短为多少”。转移时，从集合 S 中的某个城市 i，去往一个未访问过的城市 j，更新状态：

dp[S | (1<<j)][j] = min( dp[S][i] + dist[i][j] )

这里集合 S 用二进制位表示，状态数量是 O(2^n * n)，转移枚举是 O(n)，总复杂度 O(2^n * n^2)。不要被指数吓到，实际工程中n不超过20时，这个DP基本能在合理时间内跑完。

我建议对这个模型做一次手推：假设有3个客户点，编号0为配送中心，先算只访问一个客户的 dp 值，再算访问两个客户的 dp 值，最后算访问三个客户并回到起点的答案。走完这个过程，你会直观看到状态集合是怎么“扩圈”的，也会理解为什么状态压缩DP是许多路径规划算法的精确解法。

有一点特别想提醒：状态压缩DP里，集合S的枚举顺序必须从小到大，因为小集合的状态会被用来更新大集合。这和线性DP“从小到大跑”的本质完全一致，只是这里的大小关系是用二进制整数的大小来体现的。

4.3 更贴近产业的车辆调度：约束怎么融进去

真实的车辆调度问题，约束远不止“走一圈”这么简单。我们来看几个典型约束怎么在DP框架里扩展。

载重约束很容易理解：配送车有容量上限，把一个客户放入访问集合时，需要维护当前累计载重，可以在状态维度里增加一个“当前剩余容量”，代价是状态数量变多。时间窗约束则需要记录当前时间，判断下一位客户是否在时间窗内可被服务。续航/充电约束在电动汽车调度里尤其重要，需要在状态里记录当前电量，当一个客户点有充电站时，允许“访问客户+充电”的组合决策。

说实话，把所有这些约束都直接塞进DP，状态维度会爆炸。所以工程上的常见策略是两条腿走路：用DP或分支定界处理规模较小的精确求解；当规模变大时，用遗传算法、模拟退火、邻域搜索这类启发式方法。DP在这里的角色经常是“把局部子问题算到最优”，比如固定一组客户后，用DP算出城市间最优拜访顺序，再交给上层算法做分配。

这里我想分享一个真实项目里的体会：很多人一上来就想做一个全能的调度算法，结果被各种约束压得动弹不得。更好的做法是先做一个不考虑约束的最小模型，把核心DP跑通，再逐个加入约束并观察状态量变化。每加一种约束，记录一次运算时间，这样才能清楚地知道瓶颈在哪里，而不是陷入“全是if else”的泥潭。

4.4 从会做DP到会设计DP：工程迁移的3个心得

把算法题的经验迁移到工程问题上，我觉得有三个心得特别值得说。

第一个心得是“状态维度是付费的”。在OJ上写DP，状态维度开三维四维无所谓，工程上每一维都意味着内存和时间的成倍增长。所以设计状态时，优先选最小的必要维度，能用一维绝不硬上二维，用不上的维度不要塞进状态里。

第二个心得是“约束可以拆开处理”。不要试图让一个DP同时满足所有约束，可以把约束拆成两部分：硬约束（比如载重上限）在状态转移时判断，软约束（比如偏好平稳驾驶）在最终目标函数里加权。这样DP方程会更干净，也更容易调试。

第三个心得是“能用记忆化就用记忆化”。工程场景里问题结构可能随时变化，比如客户数变了、路况变了，写一个通用的递归+记忆化框架，比写一个需要精确循环顺序的迭代递推更容易维护。因为递归版本只负责“从状态到状态”的映射，调用顺序让系统栈自动处理，这在充满不确定性的业务需求下是很大的优势。

5. 常见问题与调试技巧实录

5.1 一看就会一写就废的5个原因

刷DP题最沮丧的时刻，莫过于“思路对着，代码就是错”。我总结过新手最容易踩的5个坑，在这里列出来，每个都是带过学生以后印象深刻的真实案例。

一是状态定义不完整，只写“dp[i] 表示最大值”，没说明“前i个”“以i结尾”还是“恰好等于i”，写转移时就会反复试探，改来改去。二是初始化方向理解错，求最小值却用0初始化，导致所有状态都是0，永远更新不了。三是循环顺序不对，算 dp[i][j] 时，依赖的 dp[i][j-1] 或 dp[i-1][j] 还没算好，这在二维DP里非常常见。四是数组越界，特别是访问 dp[i-1][j-1] 这类下标时没判断 i==0 或 j==0。五是类型溢出，路径计数、方案数、最大值累加动辄超过int上限，但很多人习惯性用int，导致大样例WA。

我每次接到“帮我看代码”的请求，第一句话都是：先把你状态定义的中文描述写出来，再贴代码。大多数情况下，对方写到一半自己就发现问题了。这个过程很神奇，它说明很多错误不是“不会写”，而是“没想清楚”，而把想法语言化，是逼自己想清楚的最快方式。

5.2 调试DP的独门方法：打表加手推加对拍

DP调试的通用方法，简单来说就三个字：打表、手推、对拍。

打表不是打印最终答案，而是把dp数组的中间过程打印出来。比如二维LCS，每算完一行就输出当前dp矩阵，和手推的表格对照。一旦某一格对不上，错误位置会立刻暴露，然后可以聚焦分析那个格子的转移来源。这个方法在调试二维DP时简直是救命稻草。

手推是指准备一个n不超过5的小样例，完全人工模拟DP过程，把每一步的值写在纸上。小规模数据下，任何边界问题、方向问题都会现出原形。大样例看不出错误在哪，小样例才是定位错误的关键工具。

对拍则是写一个绝对正确的暴力程序，随机生成小数据，不断比较暴力结果和DP结果。这个方法对LIS、LCS这类可暴力验证的题尤其有效。我的习惯是本地写一个 gen.cpp 生成随机数据，一个 brute.cpp 跑暴力，一个 dp.cpp 跑正解，三个文件配合循环对拍，基本能在五分钟内找到隐藏的错误。

5.3 空间优化与代码习惯

空间优化是DP里绕不开的话题，常见手段有滚动数组和降维。滚动数组适合“当前状态只依赖前一行或前一个状态”的情况，比如数字三角形自底向上时，可以用一维数组反复覆盖，dp[j] = max(dp[j], dp[j+1]) + triangle[i][j]，直接把二维省成一维。

降维更隐蔽，常见于0/1背包。二维状态 dp[i][j] 表示前 i 个物品、容量为 j 的最大价值，转移只依赖 i-1 行，所以可以去掉第一维。但这时内层循环必须从大到小枚举容量，因为 dp[j] 要用的其实是上一轮的 dp[j-w[i]]，从大到小能保证它还没被当前物品更新过。这个细节我见过太多人写反，一写反就变成完全背包，结果全错还看不出原因。

代码习惯方面，我强烈建议每个DP题都写上状态定义注释。比如：

dp[j] // 容量为j时能装的最大价值，滚动使用，注意j从大到小

这三行注释看起来普通，但能帮自己在一周后回看代码时快速进入状态，也能帮别人review时少翻来回。好的代码不是写得多么花哨，而是让读代码的人不需要猜。

5.4 常见问题速查表

我把DP调试里遇到的高频问题整理成一张速查表，方便卡住时自查。

这张表不是万能药，但它覆盖了DP初学阶段80%的报错原因。如果你遇到的问题不在表里，大概率是状态定义本身就不成立，那就要回到问题本身重新拆解，而不是继续在代码层面打转。

最后再分享一个我坚持了很久的习惯：每AC一道DP题，我都在题解边上用三行话记录状态定义、转移方程、和边界条件。半年后回头看，这就是我自己搭起来的“模型库”，遇到新题先从模型库里找相似结构，设计状态的速度会快一大截。如果你现在刷洛谷动态规划题单觉得吃力，不用急，DP确实是少数刷够量就会开窍的东西，但前提是每道题都逼自己先写状态、再写代码，这个过程千万不能省。希望这篇part11，能帮你把从“看懂”到“会写”的那根线，真正理顺。