企业官网建设流程全解析

动态规划这四个字，很多人第一次听到是在准备算法面试的时候，然后就被“状态”“转移”“无后效性”这一串术语劝退。我带过几个刚入行的同学，也帮人复盘过面试挂掉的原因，发现一个共性：大多数人不是不会写动态规划的代码，而是压根不知道该不该往这个方向想。他们背下了爬楼梯的模板，遇到背包就懵，遇到稍微换个包装的题就觉得是“另一种算法”。其实动态规划本身没什么神秘的，它解决的核心问题就一句话：把一个大问题拆成一串互相有交集的子问题，算过的就不再算第二遍。这个思路朴素到不需要任何数学背景就能理解，难点在于怎么把题目描述翻译成一张可以按顺序填满的表。

这篇内容我想把它彻底讲透，从“为什么递归会慢”开始，一路走到“怎么把二维表压成一维数组”，中间穿插几道典型题的完整推导过程和调试手法。适合两类人看：一类是刚接触算法、被动态规划卡住的初学者，另一类是有一定基础但每次遇到新题都不敢下手的同学。我会尽量少用公式，多用“最后一步是什么”“这张表该从哪往哪填”这种能直接上手的问法，把我自己踩过的坑和后来总结的判断经验都摊开讲。

1. 动态规划到底在解决什么问题

很多人学动态规划的第一个误区，是把它当成一套固定的代码模板去记。实际上它更像一种“记账习惯”。你想想生活里的场景：公司报销，同一张发票你不会重复提交；做饭时切好的配菜，你不会因为要下锅了再切一遍。动态规划做的事情就是把“已经算出来的中间结果”存起来，后续需要时直接查表。这个动作听着简单，但它能带来的效率提升是数量级的。

1.1 递归为什么会慢：重复子问题才是真正的成本

先看一个最经典的例子，求斐波那契数列第 n 项。按定义直接写递归，代码短得让人有安全感：

def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)

这段代码在 n 等于 35 左右的时候就已经明显卡顿了，n 到 45 基本就是几分钟级别。原因不是这段代码写得丑，而是它把同一件事反复做。计算 fib(5) 需要 fib(4) 和 fib(3)，计算 fib(4) 又需要 fib(3) 和 fib(2)，注意这里的 fib(3) 被算了两遍。往下展开，重复的规模会像滚雪球一样膨胀，整个调用树的节点数大约是 2 的 n 次方级别。

我做过一个粗略的统计，n 从 30 涨到 40，递归调用次数大约翻十倍，耗时也跟着翻十倍左右。这种增长曲线意味着你多给它加 5，程序可能就多跑十几分钟。而如果用一张数组把算过的结果记下来，每个位置只填一次，n 多大都只做 n 次加法。这就是重复子问题带来的差距，不是常数级的优化，是量级上的碾压。

从这张表能看出一个关键点：记忆化搜索和递推填表的时间复杂度一样，区别只在常系数和写法习惯。所以别被“动态规划必须写成循环”这种说法唬住，递归加缓存同样属于动态规划的实现形式，只是大部分人后来更习惯写循环，因为循环没有递归深度限制，也更容易做空间压缩。

1.2 什么时候该想到动态规划：三个识别信号

判断一道题该不该用动态规划，我自己常用的方式是扫三个信号。三个都命中基本就可以确定方向，命中两个值得试一试，只命中一个通常还有更简单的解法。

第一个信号是最优子结构。意思是，大问题的最优解可以拆成若干子问题的最优解拼起来。比如你要算走到第 10 级台阶有多少种走法，那它的答案必然由“走到第 9 级”和“走到第 8 级”两种情况汇总而来，中间不存在第三种来源。反过来，如果子问题之间的解无法直接组合，比如要求“路径上不能出现重复节点”，那就得多加一维状态去记录走过哪些点，问题性质就变了。

第二个信号是重叠子问题。就是前面说的重复计算。如果所有子问题都是全新的、互不相交，那更适合分治，没必要建表。像归并排序，左右两半各自独立，合并完就结束，不存在重复计算，所以它不属于动态规划。

第三个信号是无后效性。这个词听起来玄，翻译过来就是：一旦某个状态确定了，后续的决策只跟这个状态本身有关，跟你怎么走到这个状态的路径无关。比如背包问题里，只要当前已经用掉的容量和已经考虑的物品数量确定，剩下的最优选择就确定了，至于前面是先放物品 A 还是先放物品 B，不影响后续判断。如果题目要求“必须按某个特定顺序选取”或者“前面选了什么会影响后面能不能选”，那状态里就得额外带上这些信息，无后效性被破坏，转移方程会变得非常臃肿。

提示：判断无后效性最直接的办法，是问自己“给定当前状态，我还需要知道历史吗”。如果答案是需要，说明状态定义缺了信息，得补维度。

1.3 动态规划跟贪心、分治、回溯的边界在哪

这四个东西经常被混着讲，导致初学者一遇到“求最优解”就条件反射往动态规划上套。我用一张表把它们的本质区别摆清楚，后面遇到题可以对着看。

一个实用的判断顺序是：先看能不能贪心（如果能证明局部最优即全局最优，代码最短），不行就看子问题是否重叠，重叠就上动态规划，不重叠就分治，如果连最优子结构都没有、只能穷举，那就是回溯或者搜索。这个顺序我在实际做题时基本是下意识执行的，能省掉大量“想复杂了”的时间。

另外补充一个常被忽略的点：回溯加记忆化之后，本质上就是动态规划的一种写法，也就是自上而下的记忆化搜索。所以这两者不是对立关系，很多题你从回溯入手，发现重复子问题严重，加上一个缓存数组，就顺势变成了动态规划。我个人的习惯是先用回溯把思路理清楚，再决定要不要改写成递推。

2. 拆解动态规划的四个核心动作

动态规划的解题过程可以拆成四个固定动作：定义状态、写转移方程、处理边界、确定遍历顺序。这四步里任何一步出错，代码要么答案错，要么死循环。我见过太多人卡在第一步，状态定义得含糊，后面全是硬凑。这一节我把每个动作里最容易出问题的地方单独拎出来讲。

2.1 状态定义：整个方案的成败在这里

状态定义就是用一句话说清楚“我的表里第 i 个格子代表什么”。这句话必须精确到能回答“这个格子的值是什么含义、它包含了哪些信息、它不包含哪些信息”。比如背包问题里，dp[i][j]定义为“考虑前 i 件物品、容量为 j 时能装下的最大价值”，这句话里三个要素缺一不可：考虑范围是前 i 件、限制条件是容量 j、求的是最大价值。

我总结了一个好状态的三个检验标准。第一，能覆盖所有情况，也就是最终答案一定能从某个格子里直接读出来或者简单汇总出来。第二，能写出转移关系，也就是当前格子的值能由更小范围的格子推出来。第三，维度不冗余，如果两个维度之间能互相推导，那说明有一个是多余的，删掉能让空间和时间同时减半。

新手最常犯的错误是把“过程”塞进状态。比如有一道题问“从左上角走到右下角有多少条路径”，有人会把状态定义成“走到当前格子时已经走了几步”，这就是多余维度，因为步数可以由坐标直接算出来，加进去只会让表变大好几倍，还容易在转移时漏掉情况。另一个常见错误是状态定义得太窄，比如只定义“以第 i 个元素结尾的最优值”，结果发现转移时需要知道前面元素的某些信息，只能回头补维度，代码越写越乱。

提示：状态定义写完先别急着写代码，拿笔在纸上手算两三个小规模案例，看每个格子的值是否符合你的定义。这一步花三分钟，能省掉半小时的调试。

2.2 状态转移方程：从最后一步倒推最省力

写转移方程有个我认为最好用的思考方式：不要想“怎么从前往后推”，而是问“到达这个状态的最后一步有哪几种可能”。这个视角的切换非常关键，因为“最后一步”往往是有限的几种情况，枚举起来很自然。

以爬楼梯为例，到达第 n 级台阶的最后一步只有两种可能：从第 n-1 级跨一阶上来，或者从第 n-2 级跨两阶上来。所以dp[n] = dp[n-1] + dp[n-2]，一行就出来了。再看背包问题，考虑前 i 件物品、容量 j 时，最后一步对应的是“第 i 件物品到底放不放”。不放，答案就是dp[i-1][j]；放，答案就是dp[i-1][j-w[i]] + v[i]。两种情况取最大值，转移方程自然成形。

这个方法的普适性很高，因为它把“构造答案”变成了“枚举最后一步”，思维负担小很多。我遇到比较复杂的题，比如区间合并、字符串编辑距离，也是先问最后一步：编辑距离里，最后一步要么是删掉一个字符，要么是插入一个字符，要么是替换一个字符，三种情况一一对应三个转移来源，写出来几乎不需要额外思考。

需要提醒的是，转移方程写完后要检查是否覆盖了所有合法情况，有没有漏掉某种“最后一步”。曾经有一道题我漏掉了“最后一步什么都不做”的情况，导致答案偏小，排查了很久才发现是转移不完整。所以写完之后，对着小规模数据把每个格子的来源手工核对一遍，是很值得的习惯。

2.3 边界与初始化：返回 0 还是 1 的坑最多

边界处理是动态规划里最容易被轻视、又最容易出错的地方。转移方程负责主体逻辑，边界负责让这个逻辑能启动。边界设错，整张表从第一格就歪了。

初始化的时候要先想清楚“空的情况”代表什么。容量为 0 时能装的价值是 0，这是自然的；考虑 0 件物品时能装的价值也是 0；但如果题目问的是“凑出金额有多少种方案”，那金额为 0 时的方案数应该是 1（什么都不选也是一种方案），而不是 0。这个 0 和 1 的区别，坑过无数人。我自己的做法是：拿到题先问“我的状态在规模为 0 时的语义是什么”，然后根据语义决定填几，而不是凭感觉。

求最小值的问题还有一个坑，初始化成 0 会导致所有答案都变成 0，因为取 min 的时候 0 永远最小。这类问题通常要初始化为一个足够大的数，比如float('inf')或者一个题目数据范围之外的常数。反过来求最大值时，如果方案允许为空，初始化为 0；如果不允许为空（必须选至少一个），就得初始化成负无穷，否则非法方案会被当成合法方案参与比较。

2.4 遍历顺序与答案位置：填表方向决定正确性

遍历顺序不是随便定的，它必须满足一个硬约束：计算当前格子时，它所依赖的格子必须已经算好了。这句话听起来像废话，但实际写代码时经常翻车，尤其是在做空间优化之后。

举个典型例子，二维背包问题，dp[i][j]依赖dp[i-1][j]和dp[i-1][j-w]，都在上一行，所以外层循环遍历物品、内层循环遍历容量，从前往后填没问题。但一旦压缩成一维数组，依赖关系就变成了“当前值依赖同一行的更小下标”，这时候如果还从前往后填，就会用到已经被当前物品更新过的值，相当于同一件物品被放了多次。所以必须改成从后往前填。

区间类问题又是另一种情况，比如“合并石子”这种，dp[i][j]依赖比它更短的区间，所以遍历顺序要按区间长度从小到大来，而不是按左端点。我第一次写这类题的时候按左端点遍历，结果用到了还没算出来的值，答案全是错的，排查了半天才反应过来是顺序问题。

答案位置同样需要确认。有的题答案是dp[n]，有的是dp[n][m]，有的是整张表里的最大值（比如最长递增子序列，答案不一定在最后一格）。这个必须在写代码前就确定，否则很容易出现“逻辑都对，就是输出错”的情况。我的习惯是在纸上把最终答案那格圈出来，写完代码再核对一遍。

3. 从零实现：三道题的完整推导与代码现场

理论讲完，得落到代码上。这一节我选三道有代表性的题，从最朴素的思路开始，一步步推到最终版本，中间把每一次改写的原因说清楚。这三道题分别覆盖了一维递推、二维压缩、以及“动态规划不是唯一解”的情况，基本能覆盖大部分入门题型。

3.1 爬楼梯：把递归改写成递推的最小样本

题目很简单：每次可以走 1 级或 2 级台阶，问走到第 n 级有多少种走法。先写递归版本，验证思路：

def climb(n): if n <= 2: return n return climb(n - 1) + climb(n - 2)

n 小的时候没问题，n 到 40 就开始卡。原因上一节讲过，重复子问题。改写成递推，用一个数组存结果：

def climb(n): if n <= 2: return n dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

时间复杂度 O(n)，空间 O(n)。再进一步观察，dp[i]只依赖前两个值，所以整个数组其实是浪费的，两个变量就够：

def climb(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b

空间降到 O(1)。这里有个细节值得说：a, b = b, a + b这一行利用了 Python 的元组同时赋值，右边先整体求值再赋给左边，所以不会出现 a 被提前覆盖的问题。如果用其他语言写，得借助一个临时变量，顺序搞反就会算错。这就是我常说的“语言特性带来的坑”，看着是同一行代码，换个语言就得改写法。

3.2 背包问题：一维滚动数组的容量倒序

0-1 背包是动态规划的招牌题。有 n 件物品，每件有重量 w 和价值 v，背包容量为 C，每件物品最多选一次，求最大价值。

二维版本最好理解，dp[i][j]表示考虑前 i 件物品、容量为 j 时的最大价值：

def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = weights[i - 1], values[i - 1] for j in range(capacity + 1): dp[i][j] = dp[i - 1][j] if j >= w: dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v) return dp[n][capacity]

这段代码逻辑清晰，但空间是 O(n*C)，物品多、容量大的时候内存吃紧。观察转移方程，第 i 行只依赖第 i-1 行，所以可以只保留一行，边算边覆盖。但覆盖的时候有个顺序问题：如果 j 从小到大遍历，dp[j-w]可能已经被当前物品更新过了，相当于这件物品被放了两次，那就变成了完全背包。所以必须让 j 从大到小遍历：

def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[capacity]

内层循环的下界是w - 1，因为range是左闭右开，写成w - 1刚好让 j 取到 w。这个细节我见过不少人写成w，导致重量恰好等于容量的物品被跳过，答案偏小。改完之后时间复杂度不变，空间降到 O(C)。

提示：如果题目变成每件物品可以选无限次（完全背包），内层循环反过来从小到大遍历即可。这个方向差异背后的原理，下一节专门讲。

3.3 最长递增子序列：从 O(n²) 到 O(n log n) 的取舍

最长递增子序列（LIS）是一道很能体现“动态规划不是唯一解”的题。给定一个数组，求最长严格递增子序列的长度。

先用标准动态规划。状态定义为“以第 i 个元素结尾的最长递增子序列长度”：

def lis(nums): if not nums: return 0 n = len(nums) dp = [1] * n for i in range(1, n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

注意最后返回的是max(dp)而不是dp[n-1]，因为最长的那条子序列不一定以最后一个元素结尾。这个点很多人第一次写会错。时间复杂度 O(n²)，n 到几千还行，上万就悬了。

另一种做法是维护一个辅助数组tails，tails[k]表示长度为 k+1 的递增子序列的末尾元素最小值。遍历每个数字，用二分查找找到它在tails里应该替换的位置：

import bisect def lis_fast(nums): tails = [] for x in nums: pos = bisect.bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails)

时间复杂度 O(n log n)。这两种写法怎么选？我的经验是：如果只问长度，用二分版本；如果问具体是哪个子序列，或者需要输出方案，那就得用 O(n²) 的版本，因为tails数组在替换过程中会丢失原始路径信息。这是典型的“时间换信息”取舍，很多优化技巧都是这个套路，先想清楚你到底需不需要那些被丢掉的信息。

bisect_left和bisect_right的选择也有讲究。严格递增用bisect_left，这样相等的元素会替换掉原位置而不是追加，保证序列严格递增；如果题目要求非严格递增（允许相等），就换成bisect_right。这个差异在某些题目的边界用例上会体现出来，测试的时候记得专门构造含重复元素的数组验证。

4. 空间优化与常数优化：把内存从 O(n²) 压到 O(n)

动态规划写出来能过，和写得好，是两回事。很多题的时间复杂度没法再降，但空间往往有明显压缩余地。空间优化不只是省内存，它还能提升缓存命中率，实际跑起来更快。这一节讲清楚压缩的适用条件、操作手法，以及什么时候不该压。

4.1 滚动数组的适用条件与改写方法

滚动数组的本质是：如果计算第 i 层只依赖第 i-1 层，那前面的层就没必要留着，用一个一维数组反复覆盖即可。判断条件很直接，看转移方程里出现的下标是不是只有i和i-1，如果出现了i-2，那就得保留两行，以此类推。

改写的步骤我一般是三步。第一步，确认依赖层数，只依赖上一层就用一维，依赖上两层就用两个一维数组轮换。第二步，确定遍历方向，如果压缩后同一行的值会互相依赖，就要考虑倒序或者额外保存旧值。第三步，用一个小规模数据对拍，把二维版本和一维版本的输出比一遍，确认没改坏。

轮换两个数组的写法在处理依赖上两层的题时很好用，比如某些带“不能连续选”约束的题。写法上可以用下标取模，dp[i % 2][j]，也可以直接开两个变量名互换。前者代码紧凑但可读性差一点，后者更直观。我个人偏向后者，因为调试的时候能一眼看出当前用的是哪一层。

4.2 倒序遍历的本质：防止同一物品被重复使用

背包那节提到了倒序，这里把原理彻底讲透，因为这是最容易记混的知识点。

一维数组压缩后，dp[j]在更新前存的是“上一层的值”，更新后存的是“当前层的值”。计算dp[j]需要用到dp[j-w]。如果 j 从小到大遍历，那么计算dp[j]的时候，dp[j-w]因为下标更小，已经被本轮更新过了，它现在代表的是“当前层”的值，也就是已经考虑过当前物品的状态。这就等于在当前物品的基础上又放了一次当前物品，物品被重复使用了。

如果 j 从大到小遍历，计算dp[j]时，dp[j-w]还没被本轮碰过，仍然是上一层的值，语义正确。所以倒序保护的是“每件物品只用一次”这个约束。反过来说，如果题目本来就允许物品无限次使用，那正序遍历恰好就是你要的效果，不用改。

这个逻辑我建议不要死记，而是拿一个只有两件物品、容量为 5 的小例子，把正序和倒序的过程各手推一遍，看着数组怎么变，比看十遍文字解释都管用。我当时就是手推了两遍才彻底记住，之后再没搞混过。

4.3 什么时候不该做空间优化

空间优化不是越多越好，有些场景强行压缩反而得不偿失。

第一种是需要回溯具体方案的时候。比如背包问题要求输出选了哪些物品，压缩成一维之后，中间状态全被覆盖了，没法倒推。这时候要么保留二维表，要么额外开一个记录数组存决策，后者其实也没省多少空间。

第二种是依赖关系复杂、压缩后遍历顺序极难理清的时候。我遇到过一道多维约束的题，压缩后需要三层倒序加一个临时变量，代码写出来自己都不敢改，这种时候多花的那点内存完全不值当。可读性和可维护性在工程里是硬指标，算法题里也一样，写出来的代码三天后自己看不懂，那就是负资产。

第三种是数据规模本来就小的情况。n 只有几百，二维表也就几万个格子，压缩带来的收益微乎其微，反而增加了出错概率。优化的前提是先测出瓶颈在哪，凭感觉优化往往优化错了地方。

5. 常见问题与排查实录

动态规划的调试体验普遍不好，因为出错的时候往往没有报错，只是答案不对，而且不对得很隐蔽。这一节我把这些年遇到的高频问题整理成速查表，再讲几个实用的排查手法。

5.1 高频错误速查表

这张表我基本是遇到问题就扫一遍，命中率挺高。尤其是“答案偏小”和“完全背包写反”这两条，新人踩的概率极高。

5.2 调试手法：把表打印出来，用暴力对拍

动态规划调试的第一招，是把整张表打印出来看。别嫌原始，这招最有效。我通常会在小规模数据上跑一遍，把每一行打印成一行数字，然后对照手算的结果找第一个不一致的格子。第一个错的格子往往就是问题所在，它后面的错误都是连锁反应。

第二招是写一个暴力解法对拍。规模取 n 在 8 到 12 之间，随机生成几百组数据，两边跑，输出不一致的就打印出来。暴力解法用递归穷举就行，慢没关系，规模小。这招能揪出绝大多数边界错误和转移遗漏，比盯着代码看效率高得多。

第三招是给状态加日志。如果怀疑某个格子的来源有问题，就在赋值的地方加一句打印，把候选值和最终选择都输出。有时候你会发现某个候选值根本没被考虑，那就是条件判断写漏了；有时候会发现候选值是负数或者异常大，那就是初始化或者越界问题。

提示：对拍的时候一定要用固定随机种子，这样复现问题方便。另外记得把出错的那组输入原始数据保存下来，别只存结果。

5.3 复杂度估算与超时判断

写之前先估一下复杂度，能避免大量无用功。常用的经验值是：每秒大约能跑一亿次简单运算。所以 n 在 1000 左右，O(n²) 是一百万次，很安全；n 到 10 万，O(n²) 就是一百亿次，必然超时，得想办法降到 O(n log n) 或者 O(n)。

动态规划的空间也要估。dp[10000][10000]这种写法在 Python 里会直接撑爆内存，因为每个整数对象都有额外开销。真需要这么大空间的时候，要么换用数组模块，要么想办法压缩维度。我见过有同学开了个二维表，本地跑小数据没事，提交到大用例直接内存超限，回头一看是维度估错了。

还有一点容易被忽略：常数因子。同样 O(n²)，内层循环里做一次乘法和做三次函数调用，实际耗时差好几倍。如果卡在时间边界上，优化内层循环的具体写法往往比换算法更快见效，比如把重复计算的值提到循环外、减少函数调用、用局部变量代替全局访问。

6. 训练路径与复盘方法

学动态规划最怕的是“看懂了但写不出”。这个差距只能靠动手填，但填也要有方法，乱刷一通效率很低。这一节说说我自己的训练顺序和复盘习惯。

6.1 按题型分类的推进顺序

我建议按依赖结构的复杂度递进，而不是按题目热度。第一层是一维线性递推，像爬楼梯、打家劫舍这类，状态只有一个维度，转移只涉及前一两项，用来建立“状态加转移”的基本感觉。第二层是背包族，包括 0-1 背包、完全背包、多重背包，核心是理解容量维度和物品维度的关系，以及正序倒序的差异。第三层是序列类，最长递增子序列、最长公共子序列、编辑距离，重点是二维状态的定义和边界处理。第四层是区间类，合并石子、戳气球这类，难点在遍历顺序要按区间长度来。第五层是状态压缩和树形动态规划，属于进阶内容，等前面扎实了再碰。

每一层不必刷太多，每种变体三到五道，重点是每道都独立推导一遍，而不是看题解抄一遍。抄题解的快感很强，但迁移能力几乎为零，换个包装照样不会。

6.2 复盘方法：从“做出来”到“讲清楚”

我自己复盘时有个硬标准：能不能不看代码，把状态定义、转移方程、边界、遍历顺序这四件事完整讲出来，并且解释每个选择的原因。讲不清楚，说明理解还停留在模仿层面。

具体操作可以这样：做完一道题，隔一天再回来，拿一张白纸，从空白开始重写一遍，写完对照之前的代码看差异。差异处就是你的薄弱点，可能是边界想错了，也可能是初始化忘了。把这些差异记在一个本子上，积累十几条之后你会发现错误类型高度重复，针对性补一下就解决了。

另外一个有用的习惯是主动做变体。做完 0-1 背包，自己改一改条件：如果每件物品可以选两次呢？如果要求恰好装满呢？如果要求输出方案呢？每改一次，都得重新推一遍转移和边界。这个过程比刷十道新题更能加深理解，因为你是在已有的思维框架上做增量，而不是每次从零开始。

最后说说心态。动态规划确实有个陡峭的入门期，前两周可能每道题都要看题解，这很正常。但只要你坚持“每道题都自己推一遍状态定义”，大概二十道之后会有明显的顿悟感，看到新题能条件反射地问出“最后一步是什么”。我在实际带人的过程中发现，卡住的人往往不是不够聪明，而是跳过了手推这一步，直接看答案，导致脑子里没有建立起状态和格子之间的对应关系。

我个人在实践中的体会是，动态规划最值得投入的地方不是记住多少种题型，而是把“定义状态”这个动作练成本能。题型会变，包装会换，但“这个格子的值代表什么、它从哪来、它到哪去”这三个问题永远不变。把这三点问清楚，剩下的就是照着填表，代码反而成了最不费脑子的部分。