开篇先聊点实际的。动态规划这四个字一听到“最优子结构、重叠子问题、状态转移方程”这套标准定义很多人脑子里只剩一个词抽象。我做了这些年算法相关的工作也带过不少刚入行的新人发现大家并不是学不会动态规划而是卡在同一个地方——不知道怎么把实际问题翻译成状态和转移。这篇文章想做的就是把我这些年理解到的动态规划讲透先讲清楚它到底在干嘛再给几个能直接跑起来的经典例题最后和贪心、分治、回溯这些算法思想放在一起对比帮你建立一个比较完整的判断框架。不管你是刚刷LeetCode的初学者还是工作中遇到路径优化、资源分配这类问题的开发者这篇文章应该都能给你一点启发。1. 动态规划到底是什么1.1 从一个生活问题说起先看一个特别常见的场景你手上有一堆硬币面额分别是1、3、4现在要凑出6块钱问最少用几枚硬币。如果凭直觉很多人会选4块钱那枚剩下2块。但2块没法用现有硬币凑出来这条路走不通。再试411用了3枚。但最优解其实是33只要2枚。这种“看着局部最优结果整体不是最优”的情况就是贪心算法经常翻车的地方。如果老老实实枚举所有组合面额一多、目标金额一大组合数会爆炸根本算不完。动态规划的做法完全不同。它把“凑出6块”这个问题拆成三个小问题先凑出5块、3块、2块分别再加一枚对应面额的硬币。也就是说凑6 凑5 1枚1块凑6 凑3 1枚3块凑6 凑2 1枚4块只要知道凑5、凑3、凑2各自最少需要几枚硬币那凑6的最少硬币数就是这三个值各自加1后的最小值。这个过程可以一直往下拆直到最小的子问题凑0块需要0枚硬币。这里能看到一个关键点凑5、凑3、凑2这三个子问题本身还会被更小的子问题复用。比如凑5会用到凑4、凑2、凑1而凑2在凑5和凑6的计算里都出现了。如果不做任何记录重复计算会非常严重。动态规划的核心就是把每个子问题的答案存下来用一张表记住“凑出金额i需要的最少硬币数”后面用到时直接查表不重复算。1.2 核心概念状态、转移、边界动态规划里面有四个概念几乎所有DP题都离不开状态定义、状态转移方程、边界条件、遍历顺序。状态定义就是你要记录什么。上面的例子中dp[i]表示“凑出金额i需要的最少硬币数”。状态定义是整个DP的根定义错了后面全错。比如有些题目的状态光用一维数组存不够必须加一个维度记录额外信息这就是为什么有的DP题是二维甚至三维数组。状态转移方程就是状态和状态之间怎么推。上面例子里dp[i] min(dp[i - 1], dp[i - 3], dp[i - 4]) 1。翻译成人话就是我凑到i块钱最后一步可能是投了1块、3块还是4块选代价最小的那种走法再加上这1枚硬币。边界条件就是最小的那个子问题怎么给值。这个例子里dp[0] 0表示凑0块不需要任何硬币。边界条件给错整个表的起点就错了后面的推导全崩。遍历顺序就是先算哪个后算哪个。这里必须从dp[1]一直算到dp[6]从小到大推因为大金额依赖小金额。换个题目遍历顺序可能完全不同比如矩阵路径问题可能需要按行按列推进区间DP需要按区间长度从小到大推。遍历顺序的决定因素是状态依赖方向。1.3 一句话理解动态规划很多教材把动态规划讲成了数学公式大会我自己的理解反而很简单状态定义就是“你决定记录什么样的中间结果”状态转移方程就是“中间结果之间怎么推出来”边界条件就是“最小的问题怎么直接给答案”遍历顺序就是“先算哪些再算哪些”。把这四件事想清楚一道DP题基本就解了一半以上。这个概念层面的理解很重要因为后面任何一道经典例题本质上都是往这四个框里去套。与其背几十道题不如先把这套思维框架刻在脑子里。接下来我们看看什么样的题目适合用动态规划解。2. 动态规划的特点与适用条件2.1 两个关键性质最优子结构与重叠子问题很多资料把最优子结构和重叠子问题并列说成DP的两大特征这个表述是对的但必须把这两个性质拆开来看不然容易混淆。最优子结构指的是大问题的最优解可以由子问题的最优解组合得到。拿最短路径来说从A到C经过B如果A到C的路径是最短的那么A到B这一段也一定是最短的否则我可以换一条更短的A到B路径整体也变短了。反过来最长简单路径问题就不具备最优子结构因为子路径的选择会互相影响不能简单拼起来。重叠子问题是另一个性质的不同的大问题会共享同一个子问题。还是拿斐波那契数列举例递归算f(5)会调f(4)和f(3)f(4)又会调f(3)和f(2)这里f(3)被重复计算了两次。如果直接递归不记录计算量是指数级的但用DP把每个f(n)的结果存下来计算量直接降到线性。重叠子问题是DP能省时间的本质原因。2.2 无后效性DP成立的第三个隐藏条件前面两个性质是大多数资料都会提的但我实际刷题时发现还有一个条件同样关键只是藏在题目分析里这就是无后效性。无后效性的意思是一旦某个状态的值确定了这个状态之后怎么走只取决于这个状态本身而不取决于它是通过哪条路走过来的。说的再直白一点历史不决定未来。从状态A到状态B只要状态A存的信息是一样的不管我之前是花了三步还是五步到达A后续决策都一样。这个条件如果被破坏DP就没法直接用。我见过一个典型的例子是题目要求走格子的时候不能经过某个已经走过的点并且路径选择会影响后续可走区域。这时候光记录当前位置坐标是不够的因为“曾经走过哪些格子”会影响后面能不能走。要保证无后效性就必须把“历史信息”也塞进状态里比如升级成状态压缩DP用二进制位记录哪些格子已经走过了。这就是为什么有些题目天然是二维DP有些必须三维甚至更高维。所以做DP题的时候除了问“这个状态怎么定义”还要问“这个状态能不能覆盖解题所需的所有信息”。2.3 快速判断一个题是不是DP题如果你是新手看到一道题不知道怎么判断该不该用动态规划我提供一个比较机械的判断流程这四步都满足大概率可以用DP解。第一问题是否可以被拆成规模更小的同类子问题。比如“凑出6块”可以拆成“凑出5块、3块、2块”这就是规模由大到小的拆解。第二子问题之间是否有重叠。如果每个子问题完全独立比如归并排序里左右两半互不相干那这更像分治而不是DP。第三能不能定义一个只依赖少量已知量的状态。这个状态要能把子问题的答案存下来并且状态数量不超过你能接受的空间复杂度。第四状态确定后后续决策是否不受前面具体走法影响也就是无后效性是否满足。题型上也有规律可循。最值问题比如最大路径和、最长递增子序列大概率是DP计数问题比如有多少种方式走到终点也大概率是DP可行性问题比如能不能凑出某个金额同样可能是DP。反过来如果题目要求输出具体的所有方案而不是方案数那通常更适合回溯而不是DP因为DP擅长回答“最优值是多少”不擅长把每一条路径都列出来。3. 三个经典例题的完整拆解3.1 最少硬币问题零钱兑换Python实现这道题对应热搜里的“动态规划最少硬币python”是入门DP必做的题目也是我前面举例用的场景。题目描述很简单给定一堆硬币面额coins和一个总金额amount问凑出amount最少需要几枚硬币如果凑不出来返回-1。状态定义dp[i]表示凑出金额i需要的最少硬币数。转移方程dp[i] min(dp[i - c] 1)其中c是小于等于i的硬币面额。边界条件dp[0] 0其他金额初始化为一个很大的数比如float(inf)表示“暂时凑不出来”。直接看代码def min_coins(coins, amount): # 用正无穷表示当前金额无法凑出 INF float(inf) dp [INF] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! INF else -1这段代码里有一个细节值得展开说内层循环遍历的是硬币面额而不是“小于等于i的任意整数”。为什么因为凑金额i的时候最后一步永远是从某个硬币面额c跳过来的所以只需要检查那些存在对应硬币面额的子问题就够了。这样做不仅省时间也更贴近“决策”的本质。如果你想打印出具体用了哪些硬币需要额外维护一个“路径数组”记录每个金额i第一次取得最优解时用的最后一枚硬币。代码如下def min_coins_with_path(coins, amount): INF float(inf) dp [INF] * (amount 1) first [-1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c and dp[i - c] 1 dp[i]: dp[i] dp[i - c] 1 first[i] c if dp[amount] INF: return -1, [] path [] cur amount while cur 0: path.append(first[cur]) cur - first[cur] return dp[amount], path复杂度方面时间O(amount * len(coins))空间O(amount)。实战中这个复杂度已经能扛很大的金额范围但如果amount达到10的8次方级别就需要考虑其他优化手段了。这段代码的价值不在于它有多高级而在于它是理解状态定义和转移方程的最佳样板。3.2 01背包动态规划二维到一维的迭代优化01背包问题也是热搜里的大户。题目描述有n个物品每个物品有重量w[i]和价值v[i]背包容量为capacity问在不超过背包容量的前提下能装下的最大总价值是多少。每个物品只能选一次这也是“01”二字的来源。状态定义用二维数组dp[i][j]表示“从前i个物品中选背包容量为j时的最大价值”。转移方程要从两个决策里选一个更大的不选第i个物品价值是dp[i-1][j]选第i个物品前提是j w[i]价值是dp[i-1][j-w[i]] v[i]。取两者最大值。def knapsack_01_2d(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w weights[i - 1] v values[i - 1] for j in range(1, capacity 1): if j w: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) else: dp[i][j] dp[i - 1][j] return dp[n][capacity]这段二维代码很好理解但存在明显的空间浪费第i行的计算只用到了第i-1行的数据更早的行根本不会再用到。这时候就能做滚动数组优化把二维数组压成一维。def knapsack_01_1d(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w weights[i] v values[i] for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]这段代码里最关键的一点是内层循环必须倒序遍历容量j。为什么因为正序遍历会让同一个物品被重复放入。dp[j - w]如果已经在本轮被更新过它表示的就是“当前物品已经选了一次”的状态再往dp[j]上叠加就等于一个物品选了两次。倒序遍历则保证dp[j - w]还是上一轮的结果也就是当前物品尚未被选取的状态这就符合01背包“每个物品最多选一次”的约束。我见过不少初学者在这地方卡很久甚至有人把倒序当成死记硬背的结论。我建议用一个具体例子手动推一遍背包容量3一个物品重量1价值2正序遍历时dp[1]先变成2接着dp[2]max(dp[2], dp[1]2)4dp[3]max(dp[3], dp[2]2)6一个物品硬生生被装进了三次完全错误。倒序遍历就不会出现这个问题。这比记结论有用得多。3.3 从TSP到车辆调度动态规划在路径优化里的实际应用热搜里还有“车辆动态规划问题”这个关键词我猜有不少人是在搜车辆配送路径优化相关的内容。这里我不准备把VRPTW那一整套建模细节全铺开那是一个非常大的专题我只想从一个经典且好上手的角度切入旅行商问题TSP它是很多车辆配送路径优化问题的基本功。TSP问题描述一个销售员需要从城市0出发经过其他所有城市恰好一次最后回到城市0求最短路径长度。暴力枚举所有排列的复杂度是O(n!)n到20就跑不动了。状态压缩DP能把复杂度降到O(n² * 2ⁿ)配合位运算可以处理n在20左右的规模。状态设计是这样的dp[mask][i]表示“已经访问过的城市集合为mask当前最后位于城市i时的最短距离”。mask是个整数用二进制位表示城市访问状态第k位为1表示城市k已经访问过。转移时从当前城市i去往一个没访问过的城市j把dp[mask|(1j)][j]更新为dp[mask][i] dist[i][j]。def tsp_dp(dist): n len(dist) INF float(inf) # dp[mask][i]: 已访问集合为mask最后站在城市i的最短距离 dp [[INF] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发只访问了城市0 for mask in range(1 n): for i in range(n): if not (mask i) 1: continue if dp[mask][i] INF: continue for j in range(n): if (mask j) 1: continue nxt mask | (1 j) dp[nxt][j] min(dp[nxt][j], dp[mask][i] dist[i][j]) full (1 n) - 1 return min(dp[full][i] dist[i][0] for i in range(1, n))这里的mask就是前面2.2节提到的“把历史信息塞进状态”的典型做法。因为TSP要求每个城市只能访问一次所以“哪些城市已经去过了”这个历史信息决定了后续决策是否可行必须记在状态里。真实车辆调度问题往往比这个更复杂有多辆车、有时间窗、有容量限制这类问题通常是状态压缩DP并结合启发式算法或者分支定界来做。但最底层的“用状态记录历史、用转移描述决策”思路和这几十行代码是一脉相承的。4. 动态规划与其它算法思想的横向对比4.1 和分治算法的区别子问题重叠与否分治和DP最常被拿来对比因为它们俩的框架长得有点像都是把大问题拆成小问题最后合并结果。但它们最本质的区别在于子问题是否重叠。分治的典型代表是归并排序。把数组从中间切一刀左右两半分别排序再合并有序数组。左半部分的排序和右半部分的排序互不相干一个子问题的结果不会被另一个子问题用到。就算用到也是作为独立的中间步骤不会重复计算同样的子问题。所以分治算法通常用递归实现不需要一个额外的表来存中间结果存了也基本用不上。DP则相反它的子问题高度重叠。以斐波那契为例递归版f(5)要算f(4)和f(3)f(4)要算f(3)和f(2)f(3)被重复算了两次。同一个f(3)在两条不同的递归路径里被反复求解。这种情况下如果不记录子问题答案复杂度会指数爆炸一旦用表记录下来复杂度立刻降到线性。那记忆化搜索又是什么它就是分治式递归和DP之间的桥梁递归框架保持“自顶向下”的写法但每算完一个子问题就存进字典或者数组下次遇到直接返回。本质上它和DP共享同一个状态记录思想只是一个从大往小递归一个从小往大递推。所以有人会跟你说记忆化搜索就是DP的亲戚这句话不严谨但方向是对的。4.2 和贪心算法的区别局部最优还是全局最优贪心算法经常被拿来和DP做选择题因为有些题既能用贪心又能用DP解比如找零钱问题在特定面额下贪心就能得到最优解但换成某些面额就会翻车。我前面举的1、3、4面额凑6就是翻车例子贪心先选4结果411用了3枚而最优解是33只要2枚。贪心的特点是“决策即永久”。每一步都选当前看起来最好的方案选了就不回头不会保留备选方案。它的优势是速度极快通常O(n)级别也不需要额外的表来记录状态所以当问题满足贪心选择性质时能用贪心就绝不用DP。典型例子是按结束时间排序的活动选择问题贪心每步选最早结束的活动最优性可以通过交换论证证明。DP的思路完全相反。它不是每一步做一个永久的决策而是“把所有可能的决策结果都保留下来从这些结果里找最优”。以零钱兑换为例DP不会在一开始就决定用哪枚硬币而是同时考虑最后一步投1块、3块还是4块把三种选择对应的子问题答案都算出来再取最小值。这种“保留多方案”的做法本质是用空间换时间的全局枚举比贪心慢但适用范围广得多。判断一个题该用贪心还是DP可以问自己一个问题局部最优的选择是否一定不会影响后面所有决策的正确性如果能严格证明贪心是对的那就用贪心如果只是“感觉对但证明不了”用DP更稳妥。面试中最怕的其实就是“感觉贪心能过但没证明结果一跑就错”。4.3 和回溯算法的区别穷举路径和状态合并回溯算法在我看来和DP是两种完全不同的“搜索哲学”。回溯走的是深度优先搜索沿着一条路走到黑走不通就回头把所有可能的方案都枚举一遍。它适合的问题通常没有重叠子问题或者子问题的解不能直接合并比如八皇后、全排列、组合求和这类输出所有方案的题。DP则不一样它走的是“状态合并”的路子。同一个子问题只算一次结果存进表里后面所有需要这个子问题答案的地方直接查表。它不关心具体路径长什么样只关心路径的“代价”或“方案数”这类聚合结果。所以DP天然不适合需要输出全部解集合的题目因为一旦要求列出每条具体路径状态合并带来的压缩就失效了你还是要把路径完整展开这时候回溯反而更自然。但回溯和DP并不是互斥的。许多复杂搜索问题里回溯会搭配“剪枝”来减少无效搜索而DP那种记录状态的思路也可以作为剪枝策略使用。比如在有环图里找最短路径暴力DFS会无限递归而记忆化搜索本质上就是“DFS外壳 DP内核”。我的建议是看到“求所有方案”用回溯看到“求最优值或方案数且状态可以合并”用DP两者都不满足但搜索空间很小可以考虑纯暴力枚举。4.4 怎么选算法一张速查表做算法题做得多了你会发现真正难的不是看懂某个算法而是面对新题时选对算法。我把自己常用的对比维度整理成一张表放在这里供你参考。算法思想核心做法子问题关系典型场景复杂度特征暴力枚举列出所有可能解不缓存状态空间极小的题最差O(n!)或O(2ⁿ)回溯DFS遍历并剪枝路径间独立八皇后、全排列、组合最差指数级剪枝后可用贪心每步选局部最优决策不回头活动选择、哈夫曼编码O(n)或O(nlogn)分治拆成独立子问题再合并子问题独立归并排序、快速排序、最近点对通常O(nlogn)动态规划状态合并记录子问题子问题重叠背包、最短路、序列匹配O(状态数 * 转移代价)这张表不是让你死记的而是给你提供一个“排查”的顺序。拿到一道题先想能不能暴力枚举状态空间大到无法接受就按重叠子问题特征往DP上靠如果发现子问题明确独立考虑分治如果能证明局部最优可以推导全局最优考虑贪心如果题目要求输出所有方案且有约束搜索考虑回溯。这个思考流程走下来绝大多数题都能有一个靠谱的初步判断。5. 动态规划的高频坑与排查心得5.1 初始化陷阱0还是正无穷DP初始化是我看到最常见的错误来源之一而且这个错误特别隐蔽不调试根本发现不了。求最小值的题目dp数组的初始值应该设成一个非常大的数比如float(inf)表示“这个状态尚且不可达”求最大值和方案数的题目初始值通常设0但dp[0]或者某些特殊边界通常单独给一个不同的初值。举一个典型的反例。实现最少硬币问题时如果dp数组初始值全部给0那么dp[1]在计算时dp[0]0dp[1]min(0, dp[0]1)1看起来没问题但dp[2]min(0, dp[1]1)0因为你拿一个没赋值的0去跟计算结果比0永远最小结果整个表全被0覆盖最后输出永远0。这种bug数据小的时候很容易发现数据一大就变成“答案偶尔对偶尔不对”非常折磨人。正确的分类记忆最值问题初始值给正负无穷代表“我不确定这个状态能不能达到但别用它来污染真实计算结果”计数和可行性问题初始值给0边界给1涉及到“是否存在解”的问题额外用一个标志数组或者把不可达状态保持为-1都可以。我的习惯是写题前先在注释里写清楚每个初始值的含义而不是写完再看这样能减少大量无效debug。5.2 遍历顺序为什么01背包要倒序完全背包要正序遍历顺序问题我在3.2节详细展开过01背包的倒序原因这里再把它放到一个更大的背景下讲遍历顺序的本质是“你希望状态更新时读到的是旧值还是新值”。01背包倒序遍历是因为dp[j - w]必须在当前物品未选过的前提下使用所以要先算大容量再算小容量保证本轮更新不会反向影响后续计算。完全背包则相反每个物品可以选择无限次所以正序遍历恰好能让同一个物品在同一次循环里被多次“叠加”进不同容量中。很多人记混这两个顺序我提供一个理解方式把容量j当成“已经放入物品后的剩余容量”。01背包里一个物品只能用一次所以你在更新dp[j]时引用的dp[j-w]必须是上一轮还没处理过这个物品的值倒序可以保证这一点。而在完全背包里这个物品可以反复使用所以你希望dp[j-w]已经是“用过了当前物品”的值正序天然满足这个需求。想清楚“更新依赖的是旧值还是新值”就再也不会记反。多维DP的遍历顺序同理。区间DP通常按区间长度从小到大遍历因为长区间的解依赖短区间树形DP通常先递归子树再处理当前节点因为父节点依赖子节点的结果。每次写转移之前问自己一句我当前要用的dp值是不是已经在上一轮被正确算出来了这比死记任何模板都有用。5.3 状态定义出错怎么办状态定义是DP题的灵魂一旦想出错的形状你后面写多少代码都救不回来。最常见的错误是状态维度不够导致无后效性被破坏。比如走格子问题如果你只记录当前位置(i,j)但题目要求不能走回头路那么“之前来过哪些格子”会直接影响后续路径是否合法这种情况下必须把“访问过的格子集合”编码进状态比如用二进制mask否则你算出来的所谓最优解很可能走了一条根本不允许走的路径。另一个常见问题是转移方程和状态定义不自洽。明明定义了dp[i]表示“以i结尾的最长上升子序列长度”写转移的时候却去找dp[i-1]直接加1这完全对不上。排查这种问题有一个很笨但很有效的方法把dp表整个打印出来手动挑几个位置用纸笔画一下转移过程看每个状态是不是严格符合定义。我曾经排查一个LIS问题的bug就是靠打印dp表逐行对照最后发现是我把“以i结尾”写成了“前i个元素”导致一整个维度的语义偏移几乎所有转移都错了一格。如果确认状态定义和转移都没问题但答案还是不对可以写一个暴力解法做对拍。小规模随机数据下把DP结果和暴力结果反复对比很快就能定位到是哪一组输入触发了差异。这个“暴力对拍”的习惯是我强烈建议每个人都养成的debug手段它比肉眼盯代码高效十倍。5.4 性能优化三板斧滚动数组、记忆化、剪枝DP写对了不代表能过题很多时候还需要优化。最基础的优化是滚动数组把二维dp压成一维把空间复杂度从O(n*m)降到O(m)。具体做法就是只保留最近需要的几行比如01背包只保留上一行区间DP有时需要保留上一区间长度层。代价是你失去了整张dp表可能无法复原具体方案所以如果题目要求输出路径不要轻易做这个压缩。记忆化搜索是另一种优化思路它和DP递推本质上等价但代码写起来更贴近原问题。当你不知道怎么安排遍历顺序时记忆化搜索可以自动处理依赖关系因为它只在你真正需要一个子问题时才去计算。代价是递归有函数调用开销而且深度太大可能栈溢出所以工程上的大型问题更倾向于显式DP递推。剪枝这个优化在回溯里讲得最多但DP里也有应用场景。有些状态明显不可达可以在转移前判断一下比如背包容量为负数的状态直接跳过有些状态确定不可能成为最优解比如当前代价已经超过已知上界就没必要继续扩展。这类剪枝一般不会改变复杂度阶数但常数优化在真实数据里往往能带来2到5倍的提升。5.5 刷题建议怎么练DP最有效从带新人的经验来看练DP有两条极端路线都不可取一条是一头扎进难题反复看题解但自己写不出来另一条是只刷简单题天天做爬楼梯和斐波那契以为理解了DP遇到真正的背包题还是懵。我的建议是分四个阶段走。第一阶段把最基础的几道题吃透斐波那契、爬楼梯、最小路径和、最少硬币、01背包。这些题目少但覆盖了DP的所有核心要素。第二阶段尝试自己打印dp表对照状态转移方程理解每个格子怎么来的做到能徒手推导一个小规模case。第三阶段按题型系统练线性DP、区间DP、背包DP、状态压缩DP、树形DP每个题型练三五道经典题重点总结状态定义的模式。第四阶段回到真题和竞赛题目训练判断“这道题能不能DP”和“状态怎么设计”的直觉。我比较反对只看题解不动手的刷法。动态规划本质上是一种思维模式看别人推导觉得头头是道自己上手就是另一回事。手推dp表、写暴力对拍、打印中间状态这些看似浪费时间的手段其实才是学DP最省时间的路径。6. 写在最后给初学者的几点经验聊了这么多最后分享一点我个人的体会。我在带新人的时候发现大家对动态规划的恐惧很大程度上来自于“状态定义”这一步——它不像排序算法那样有固定的套路每一道题的状态定义都可能完全不同这让人很没有安全感。但换个角度看这恰恰是算法的乐趣所在。我自己的经验是先不要急着写转移方程先用自然语言把状态说清楚哪怕写一段注释都行状态定义说清楚了转移方程通常就是顺水推舟的事。另外如果你在面试或者工程里遇到一道题感觉像DP但一时之间没思路不妨从小规模例子开始手推。把n等于1、2、3的结果一个一个写出来很多时候规律就藏在其中。我踩过最大的坑就是拿到题就想着套模板套不上就开始慌。其实动态规划不是模板库它是一种思维方式——用状态记录中间结果用转移描述依赖关系用边界划定起点用顺序保证正确性。把这四件事内化于心再回头看那些看似千变万化的题目会发现它们不过是同一件事的不同包装。