“动态规划”这四个字，几乎每个刷算法题的人都绕不过去。我见过太多人——包括曾经的我自己——在面对一堆“dp[i][j]”“状态转移方程”的时候，第一反应是找模板、背套路，结果换个题目立刻卡壳。这篇文章想换个角度聊：动态规划真正的难点从来不是写代码，而是“怎么想到这个思路”。我会用一套自己反复验证过的解题流程，从识别题目、推导暴力解、再到设计和优化，一步步拆开讲清楚，希望能给正在被DP折磨的人一条可以照着走的路。
1. 动态规划最常见的误读：它不是“填表大法”，而是“记忆化决策”
很多人学动态规划的第一个画面，就是看题解里别人画了一张二维表格，然后对着表格填来填去，于是下意识觉得“DP就是填表”。这是我在教学和答疑里见过的最大的误解。填表只是动态规划在“自底向上递推”阶段的呈现方式，它不是动态规划的本质，更不是解题的起点。
1.1 动态规划到底在“优化”什么
我们回到最朴素的问题。任何一个决策过程，都可以拆成若干个子步骤，每个子步骤做一次选择，最终得到一串结果。如果这个问题天然带有“当前选择会影响后续选择空间”的特性，那么暴力枚举所有选择路径就是指数级的，绝大多数情况下跑不动。
动态规划做的事，本质上是把“从这一步走到终点”的答案提前算好并缓存起来，让不同的前序路径共享同一份后续结果。
讲个生活化的类比。想象你在一座迷宫的回字走廊里，从很多个不同入口出发，最终都会汇聚到同一个岔路口，而从这个岔路口通往出口的最短距离是唯一的。那么你只需要算一次“岔路口到出口的距离”，之后无论从哪个入口进来，直接拿这个缓存值加上“入口到岔路口的距离”即可。动态规划缓存的就是这一类的“岔路口到出口”的结果。
所以，判定一个题目能不能用DP，核心不是看它有没有“状态转移方程”，而是看它有没有下面这两个结构特征：
- 重叠子问题：大问题分解出的小问题会重复出现，同一个子问题的解被多条路径需要。
- 最优子结构：大问题的最优解可以由子问题的最优解拼接得到。
这两个特征同时具备，DP才成立。
1.2 为什么“自顶向下”比“自底向上”更适合入门
动态规划有两种写法：自顶向下（递归+记忆化，也叫备忘录法）和自底向上（递推填表）。新手最大的学习误区，是一上来就直奔自底向上，直接去推那个“状态转移方程”，推不出来就卡死。
我的建议是：先学会自顶向下。因为它和我们最原始、最直觉的思考方式一样——直接用问题定义去写递归函数，加上一个缓存表防止重复计算。先写暴力递归，再加缓存，这就是记忆化搜索。等这个版本跑通了，再来考虑能不能改写成自底向上的递推。绝大多数DP题目，自顶向下版本都能AC，只是常数上稍微慢一点。而它带来的好处是：你不必在纸上凭空脑补状态转移方程，你只需要写出“当前这一步怎么利用子问题的结果”就够了。
这一点非常重要。我见过很多程序员，递归版思路很清楚，一转换到递推版就迷糊，根源在于他们跳过了“暴力递归-记忆化-递推”的中间步骤。这个路径我在第3节会完整展开。
2. 哪些题该用动态规划：三个可操作的识别信号
拿到一道题，先别急着写代码。做一次“类型判断”，比什么都重要。动态规划不是万能药，用错地方会浪费大量时间。我从实践中总结出三个可操作的识别信号，满足两个及以上，基本就可以按下DP的思路来设计。
2.1 信号一：求的是最优解、方案数、布尔可达性
这是最明显的信号。如果题目问的是“最大值”“最小值”“最长子序列”“最短路径”“方案数量”“是否可达”，这大概率是一道DP题。因为这类问题通常天然具有“合并子问题结果”的特征：整体最优由局部最优组合而来，整体方案数由分类子方案数相加而来。
反向排除一下：如果题目让你输出“具体选的是哪几个物品，而不是最大价值是多少”，这种情况下DP虽然能算价值，但回溯出具体选择通常非常繁琐，需要额外记录路径。实用性强的做法是：仅当题目只要求数值答案时优先DP；要求打印具体方案的，先评估数据规模，太小就搜索，太大再用DP加路径回溯。
2.2 信号二：子问题在递归展开时会反复出现
这一条需要画递归树才能看出来。例如爬楼梯问题，从第n阶开始递归，会展开成(n-1)和(n-2)，而(n-1)又会继续展开成(n-2)和(n-3)。这里n=10时也许不明显，但n=35时，重复计算的量级会爆炸。如果你画出递归树，发现同一个节点反复出现，那就说明存在重叠子问题。
实操判断方法很简单：先写出暴力递归，不用管性能，然后在递归函数开头打印入参，看相同参数被调用的次数。连续调用几十次就说明重叠严重。出现重复调用，说明这个题有DP的“资格”了；如果没有重复调用，说明问题分解是树状的、各子问题互不相干，这时候分治或者贪心才合适，强行DP只会画蛇添足。
2.3 信号三：无后效性——当前决策只影响未来，不反噬过去
无后效性是很多人忽略的环节，但这个概念决定了状态定义能不能收敛。所谓无后效性，指的是：一旦某个阶段的状态确定，之后的过程选择就只和“这个状态”有关，至于这个状态是怎么走到这里的，不影响未来的决策。
举一个经典的反例。假设你玩一个回合制游戏，每回合可以选择“攻击”或“防守”，但攻击之后会积累一个“眩晕值”，防守会消耗这个值。那么此时“当前回合是否清醒”这个状态不仅取决于当前的操作，还取决于前几回合的操作历史。如果直接把状态定义为“当前回合做什么”，DP就失效了，因为同一个状态背后隐含的历史不同，未来也完全不同。
克服方法也很经典：把历史中影响未来的因素“吸收”进状态维度里。在这个例子中，增加一维“剩余眩晕值”，状态变成“当前第几回合、剩余眩晕值”，这样一来，状态一旦确定，未来的决策空间就唯一确定了，无后效性恢复。我在第4节讲状态设计时会再深入说这个“吸收历史到状态”的技巧。
2.4 一票否决：贪心才是更优解的情况
有一种情况特别尴尬：题目确实具备最优子结构，但使用贪心策略就能达到同样效果，而且复杂度更低。比如“从一堆硬币里挑选最大面额使总数达到目标”——如果硬币面额满足某些特殊性质，贪心即是正确解；但大部分情况下是假命题。DP能覆盖贪心能解的部分问题，但反过来不行。
我的判断技巧是：先问自己“每一步做一个当下的最优选择，不回头调整，结果还会正确吗？”如果明显不正确（例如经典的找零问题中，面额1、3、4要凑6，贪心选4+1+1用了3枚，最优其实是3+3用了2枚），那就只能DP。如果拿不准，直接按DP处理，因为DP不会因为贪心能解就变错，反之贪心逞强却容易翻车。
3. 一条可复制的推导路径：从暴力递归到记忆化再到递推
很多同学的学习路径是反的：先看题解的状态转移方程，再照着方程填表。结果填表会了，换题就不会了。我推荐的正向路径是：暴力递归 → 递归树分析 → 记忆化搜索 → 自底向上递推。这四条路是可以一步步复制的，几乎不需要“灵机一动”。
3.1 第一步：永远先写“能算对”的暴力递归
不要一上来就想最优解。先写一个绝对正确、哪怕指数级的递归。这个版本的价值在于确认“分解逻辑”是正确的：当前问题的解，确实是由若干个更小规模的同类问题的解组合而来的。这个分解逻辑，就是未来状态转移方程的雏形。
以经典的数字三角形问题为例（给定一个三角形矩阵，从顶部向下走，每次走左下或右下，求路径上数字之和的最大值）。暴力递归可以直接写：
def max_path_sum(triangle, i, j): if i == len(triangle) - 1: return triangle[i][j] left = max_path_sum(triangle, i + 1, j) right = max_path_sum(triangle, i + 1, j + 1) return triangle[i][j] + max(left, right)这里的递归逻辑非常朴素：“当前位置的最大和 = 当前值 + 下一层的两种走法中较大的那个”。因为第i层的路径只能由第i+1层派生，分解天然成立。
3.2 第二步：画递归树，看重复计算有多严重
用数字三角形那个例子，如果你从顶部出发，目标位置(2,1)可能由(1,0)走右下来到，也可能由(1,1)走左下来到。这意味着整个递归树里，同一个节点会被多条路径访问到。越靠近底部的节点，重复访问次数越多。
画递归树是手动行为，但你可以用代码辅助验证：在函数开头加上一行print(i, j)，然后跑一个小数据，看相同参数打印了多少次。看到重复打印的瞬间，你就明白“为什么需要DP”了。这一步的核心目的，是让你从直觉上理解重叠子问题存在的位置。
3.3 第三步：加一个缓存字典，改成记忆化搜索
加缓存的步骤极其机械：在递归函数里先检查备忘录，命中就直接返回，没命中就正常计算、存好再返回。这段代码几乎不需要动脑：
from functools import lru_cache @lru_cache(None) def max_path_sum(i, j): if i == len(triangle) - 1: return triangle[i][j] return triangle[i][j] + max( max_path_sum(i + 1, j), max_path_sum(i + 1, j + 1) )这一步的收益在于：递归逻辑保持不变，只是加了缓存，时间复杂度直接从指数级降到了 O(n^2)。因为每个(i, j)组合只被真正计算一次，之后全是查询。
我强烈建议，在你还没彻底搞懂自底向上之前，考试、面试、比赛中都可以先用记忆化搜索。它几乎不会错，调试起来也直观。唯一的问题是Python递归深度有限，数据规模超过递归深度时可能爆栈。此时可以考虑改递推或者设置递归深度，不过多数题目在限制以内。
3.4 第四步：手工改写为自底向上的递推表
从记忆化搜索改自底向上，核心要做一件事：确定计算顺序。递归是从大问题出发、纵深钻进小问题；递推则反向——先把最小子问题的答案放进表格，再逐步扩大问题规模，保证计算当前格子时，依赖的那些格子已经被填好。
以数字三角形为例。最底层本来就已知，倒数第二层可以直接由最底层计算，这样一步步往上推，表格下标从大到小或从小到大，方向必须保证依赖已具备。改写后：
def max_path_sum_bottom_up(triangle): n = len(triangle) dp = [row[:] for row in triangle] for i in range(n - 2, -1, -1): for j in range(i + 1): dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]) return dp[0][0]为什么自底向上往往更受推崇？因为省掉了递归调用的开销，也能用滚动数组继续省空间，而且很多题目在递推视角下，转移顺序更清晰，不容易递归爆栈。
3.5 为什么不能跳过前面的步骤直接写转移方程
我承认，高手确实可以看一眼题目直接写出转移方程，但那是大量训练之后的内化结果，不是初学者的路径依赖。直接套转移方程的最大问题是：你根本不理解这个方程为什么长这样，一旦题目加一个限制条件，比如“必须恰好使用k个元素”，状态维度立刻要变，方程也得大改，死记硬背的人当场崩溃。
我的建议是：前期做题永远走完整条路径，哪怕想出了递推写法，也在草稿纸上画一遍递归树。等熟练了，大脑里可以自动完成“暴力递归-缓存-递推”的瞬时映射，这时候直接写递推也不迟。这个习惯能保证你对每个状态定义、每个转移方向都有扎实的理解，不会出现“照着题解能过，独立做一个新题就卡壳”的情况。
4. 状态设计的思考起点：“最后一步”和“问题规模”双抓手
如果问做DP题最卡人的环节是什么，十个人里九个会说是“状态定义”。状态定义就是给dp数组的每个维度赋予含义。它决定递推能否成立，也决定空间复杂度。这一节我分享两个自己最常用的切入维度。
4.1 从“最后一步”倒推整个子问题结构
几乎所有DP问题都可以用“最后一步”来破局：假设我们已经做完了所有决策，站在终点回看，最后一步操作是什么？它可以是从某处走过来的、选了某个物品、匹配了某个字符。只要这一步的可能情况是有限的、可枚举的，你就可以枚举它，把大问题化归成“少了一步”的小问题。
以“编辑距离”为例：从字符串A变成字符串B，最后一步无非三种操作——把A的最后一个字符删掉、在A末尾插入B的最后一个字符、把A的最后一个字符替换成B的最后一个字符。于是状态转移自然写出来：
- 删：
dp[i][j] = dp[i-1][j] + 1 - 插：
dp[i][j] = dp[i][j-1] + 1 - 换：
dp[i][j] = dp[i-1][j-1] + (1 if A[i-1]!=B[j-1] else 0)
这里的核心动作是：枚举最后一步的每一种可能性，然后每一种可能都对应一个更小的子问题。子问题的规模，通常就是去掉这最后一步后剩下的状态。所以状态定义里，把“处理到哪个位置”这个信息作为维度，是自然而然的事。
4.2 状态维度放什么：哪些“历史信息”会影响未来
每当考虑要不要加一个维度时，我的判断标准是：这个状态一旦确定，未来所有决策所需的信息是否已经足够？如果不够，说明有“历史信息”泄漏到了未来，必须把它吸收成状态维度。
经典例子是“股票买卖”问题。你决定第i天是否买入时，必须知道当前手里有没有股票——这是历史买卖操作留下的状态，它会影响今天的决策。所以状态必须加上一维“当前是否持有股票”，比如dp[i][0/1]分别表示第i天结束时不持有/持有股票的最大收益。如果不加这一维，你就无法区分“手里有货”和“手里无货”的两种情况，转移方程也无从谈起。
另一个总被忽略的点：限制条件本身就是状态维度。“最多交易k次”“恰好用m个元素”“重量不超过w”，这些限制条件实际上是决策历史的压缩记录，必须体现在维度里。比如dp[i][k]表示前i个物品中选了k个，重量不超过某个值的最大价值。很多人漏维度，原因就是只盯着“位置”看，忘了把“剩余限制”也作为维度。
4.3 边界与分类讨论：不重不漏地枚举转移
状态设计完成之后，写转移方程还要做一项自查：每种转移方式是否覆盖了从上一个状态到当前状态的所有可能路径，并且互相不重叠。如果两条路径都能到达同一个状态，且算出的值含义重复，就会造成重复计数或错误比较。
以“零钱兑换”的计数版本为例（求凑出金额amount的方案数），如果硬币面额是[1, 2, 5]，你可能会写出dp[amount] = sum(dp[amount - coin])，但这会让“1+2”和“2+1”算成两种方案，而题目如果只关心组合（不区分顺序），这就是错了。要避免这个问题，必须加上“当前用到哪一类硬币”这一维度，把组合顺序强制排掉。
边界值也永远要单独思考：状态维度里出现0怎么办？比如dp[0][0]初始化为0还是1，取决于它的含义是“没有元素时的值”还是“没有元素时的一种空方案”。这类细节，是需要结合“最后一步”的递归树从最小情况逐步确定的。
4.4 用“示例驱动”检查状态定义是否靠谱
状态设计完成之后，我建议不要急着写代码。先拿一组很小的输入，比如n=3或者金额=5，手工按状态定义推一遍表格，看看结果是否符合直觉。这一步耗费的时间很少，但能避免大量因状态定义错误而导致的返工。特别是当你发现某个格子的值不符合常识时，不要修修补补，直接回头审视状态定义。
我见过太多人定义错了状态，然后在转移方程上疯狂调试两三个小时。相比之下，花十分钟用手推一遍小样例，就能立刻发现问题。这份“慢思考换快调试”的耐心，是DP题做得快的人共同的特点。
5. 空间优化的尺度：什么时候该滚，什么时候别滚
空间优化是DP题里最容易被过度追求的一件事。滚动数组、原地修改、状态压缩，写出来确实赏心悦目，但对于初学者，我建议把优先级往后放：先把时间和空间都正确的版本写出来，再谈优化。不过，理解优化的原理本身，能反过来加深你对状态依赖关系的认识。
5.1 滚动数组的本质：只保留“未来还会被参考”的状态
滚动数组的出发点是：自底向上填表时，计算dp[i][:]只需要依赖dp[i-1][:]或更早的固定几行，那些已经不会被再参考的旧行，完全可以覆盖掉。这样二维表被压缩成了一维或者两维交替使用，空间从O(n*m)降到O(m)。
一个最典型的例子就是数字三角形。计算第i层时只依赖第i+1层，所以只需要开一个一维数组，从最底层开始，每计算完一层就在原数组上覆盖下一层的值，方向从前往后即可。这属于“十分安全”的压缩：因为旧值用完即丢，没有二义性。
5.2 什么时候优化会引入隐蔽的bug：依赖方向和覆盖顺序
最麻烦的情况出现在“同一维数组既要当旧状态、又要当新状态”的时候。以0/1背包为例，dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，这里的dp[j]是当前行的值，而dp[j - weight[i]]理应是上一行的值。如果你直接从左往右遍历j，计算dp[j]时使用的dp[j - weight[i]]已经被本轮更新过，等于允许同一个物品被取多次——这就变成了完全背包，而不是0/1背包。
解决办法是从右往左遍历：因为j - weight[i]小于j，从右往左时它还没有被本轮更新，读到的还是上一行的旧值。这一正一反的遍历顺序，是无数人踩过的坑。这里我要强调：不彻底理解这个原因，只记“0/1背包倒序遍历、完全背包正序遍历”的口诀，遇到变种题就会再次翻车。
5.3 我的使用习惯：默认不压，需要时才动手
我的实践原则很简单：题目空间限制宽松时，直接用二维dp，代码可读性优先。空间限制压到很小，或者维度大到必须压缩，才考虑滚动数组。而且每做一次压缩，必须用同一个样例在草稿纸上模拟覆盖过程，确认没有覆盖未使用的旧值。
另外，转移方程依赖“前k行”时，可以用环形数组或者k个一维数组交替，不要硬压成一维。过度压缩带来的脑力负担，往往高于空间节省带来的收益。尤其实战比赛中，时间宝贵，“能过”永远比“优雅”优先级高。
6. 三个高频模型的完整推导：计数型、选择型、序列比对型
动态规划虽千变万化，但大部分题目可以归入几个“母模型”。熟练吃透下面这三个母模型，遇到变种题就能快速迁移。我会完整走一遍从状态定义到转移方程的推导过程，而不是只贴最终公式。
6.1 计数型母模型：爬楼梯及其变种
爬楼梯问题表面简单，但它代表了“阶段性计数”的一整类DP。状态定义：dp[i]表示到达第i阶的不同方法数。用“最后一步”思维来看，到达第i阶，最后一步不是从i-1跨1步，就是从i-2跨2步，因此dp[i] = dp[i-1] + dp[i-2]，且dp[1]=1, dp[2]=2。
这个模型可以扩展到“每次能跨1步、2步或3步”，方程变成三项相加；也可以扩展成“某些台阶不能落脚”，只需要把那些格子置0；甚至可以是“每一步消耗体力，求最小体力消耗”，那就换成取min而不是求和。爬楼梯模型的变种之所以层出不穷，是因为它的状态维度和转移结构足够简单，很适合当作理解DP的起点。
6.2 选择型母模型：0/1背包与多重维度
0/1背包是“选择型”DP的黄金样本。状态定义不用二维就会漏信息：dp[i][j]表示前i个物品，总重量不超过j时能得到的最大价值。注意，这里“前i个物品”和“总重量j”是两维，缺一不可。前者保证每个物品只被考虑一次，后者记录容量约束。
转移方程是经典的“选与不选”二分：
- 不选第i个物品：
dp[i][j] = dp[i-1][j] - 选第i个物品：
dp[i][j] = dp[i-1][j-w[i]] + v[i]综合取二者较大值。这个模型衍生出的变种包括：完全背包（每个物品无限选）、多重背包（每个物品有数量限制）、分组背包（每组选一个）、依赖背包（选主件才能选附件）。每加一种限制，本质都是“状态维度增加”或者“同层转移顺序改变”。
6.3 序列比对型母模型：最长公共子序列的双序列pos结构
最长公共子序列（LCS）代表的是“双序列配对”类别。状态定义：dp[i][j]表示A的前i个字符和B的前j个字符的最长公共子序列长度。用“最后一步”思维：比较A[i-1]和B[j-1]，要么相等，匹配之，答案是dp[i-1][j-1]+1；要么不等，则这个字符至少有一个不在LCS里，取max(dp[i-1][j], dp[i][j-1])。
这个模型看似简单，但它极其重要，因为它体现了“两个指针同时推进”的共性思维。把相同框架套到“编辑距离”上，只需在不等时增加“替换”这类操作；套到“最长公共子串”则区别在于连续性问题，匹配失败时状态清零即可。遇到任何“两个序列的最优匹配、相似度、对齐”之类的问题，都可以从这个母模型起步思考。
6.4 母模型迁移的判断技巧
拿到一个新题，别急着发明新定义，先问自己“它最接近哪个母模型”。如果选择题物品，那就是背包族；如果是走台阶、跳格子、走方格，那就是阶段计数族；如果是两个序列匹配，那就是双序列配对族。绝大多数题都是母模型的组合变体，只改一个约束条件或加一个维度。熟练掌握母模型，就等于把题海压缩成了套路集。
我发现很多刷题的人做一道记一道，却不肯花时间做“归类总结”。其实每道题做完后，花三分钟在题解旁标注“本质属于XX模型，和XX题的区别在于XX”，日积月累之后，你面对新题的反应速度会明显快于别人。
7. 刷动态规划这几年踩过的坑：从“小样本过不了”到“初值设错”
最后聊点实战层面的避坑经验。动态规划写起来行云流水，错起来也莫名其妙，而且很多错误隐藏得极深，不跑大数据都看不出来。下面这几类坑，是我在真实调试场景里反复遇到的，值得记下来。
7.1 索引越界与负下标：dp含义和数组下标的错位
自底向上递推时，最常见的错误是在转移方程里访问dp[-1]或dp[n]。Python里dp[-1]不会报错，但它访问的是最后一个元素，逻辑上完全错误，而且极难察觉。我见过不少人在“编辑距离”这类题里，因为访问了dp[i-1]而i等于0时没有做边界特判，导致计算结果偏大或偏小。
处理原则只有一个：在递推循环外层单独初始化边界行和边界列，不让他们参与转移，或者循环里显式判断索引范围。不要把“越界触发的异常”当作正常逻辑的一部分处理。边界值往往直接对应空串、零物品、零容量等“最小情况”，含义必须单独梳理清楚。
7.2 初值设错的连锁反应：为什么你的答案总是差1
初值错误会导致整个表格的“地基”偏移。最常见的两类：
- 最大值类DP，初始值一律设为负无穷，否则取max时会把从未计算过的状态当成有效值。
- 计数类DP，
dp[0]通常设为1（代表“空方案”），而不是0，否则从起点出发的所有方案都会变成0。
初值问题最好的检验方式是用最小样例手推：比如n=1或amount=0时，结果应该等于什么？如果手推和代码跑出来的不一致，百分之百是初值定义错了，不需要继续调试转移方程。
7.3 复杂度估算：写之前先算一遍表有多大
“调试半小时，提交超时”这件事，根子在于没算复杂度。DP的时间复杂度是“状态数乘以每个状态的转移数”，状态数是各个维度规模的乘积。写代码前先估算：n=1000且m=1000，那么二维表就是100万个状态，每个状态O(1)转移，整体O(10^6)，Python一秒钟内没问题。但n=10^5且状态也要10^5，再加O(n)转移，就是O(10^10)，只有理论意义，必须考虑压缩维度或换算法。
这种估算能力也是面试中的隐形加分项。你不仅给出解法，还顺手分析时间和空间复杂度，好坏高下立判。
7.4 用“小样例手推”替代“盲目打断点调试”
DP题与普通题最大的调试区别是：普通题断点看变量一眼就能发现问题，DP题表格一旦铺开，几百个格子的中间值根本看不过来。我的习惯是开着三个小样例跑，每个样例规模不超过5，然后把这些样例的表格用手工推一遍，和程序输出逐格对比。只要有一个格子不一样，顺着依赖往回倒查，很快就能定位是转移方程错还是初值错。
这个方法的思路是：把调试范围压缩到人可以手工验证的尺度。与其在1000x1000的表海里捞针，不如在三维小表上精准复核，效率高得多。长期坚持这个习惯，慢慢地你就不太需要调试了，因为你在写代码前的设计阶段已经通过手推样例把所有逻辑验证了一遍。
写在最后
动态规划是我认为“投入产出比”最高的算法主题之一：它不像数据结构那样需要背大量模板，也不像图论那样对建模能力要求极高。只要掌握“暴力递归→记忆化→递推→优化”这条路径，再用“最后一步”思维反复练习状态设计，几乎能覆盖大部分题目。
我个人的习惯是，每次遇到一道没见过的DP题，先写暴力递归，再用缓存优化，递推版本只是最后“锦上添花”的事。这个顺序可能不如直接照着状态转移方程写代码看起来“快”，但它省去了大量试错时间，也让我对每道题的理解都深入一层。如果你现在正被动态规划折磨，不妨从下一道题目开始，试着先把暴力版写出来，再画一画递归树，你会发现自己对“状态”“转移”这些概念的理解，会有一个质的改变。
