“动态规划”这四个字几乎每个刷算法题的人都绕不过去。我见过太多人——包括曾经的我自己——在面对一堆“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)。这里n10时也许不明显但n35时重复计算的量级会爆炸。如果你画出递归树发现同一个节点反复出现那就说明存在重叠子问题。实操判断方法很简单先写出暴力递归不用管性能然后在递归函数开头打印入参看相同参数被调用的次数。连续调用几十次就说明重叠严重。出现重复调用说明这个题有DP的“资格”了如果没有重复调用说明问题分解是树状的、各子问题互不相干这时候分治或者贪心才合适强行DP只会画蛇添足。2.3 信号三无后效性——当前决策只影响未来不反噬过去无后效性是很多人忽略的环节但这个概念决定了状态定义能不能收敛。所谓无后效性指的是一旦某个阶段的状态确定之后的过程选择就只和“这个状态”有关至于这个状态是怎么走到这里的不影响未来的决策。举一个经典的反例。假设你玩一个回合制游戏每回合可以选择“攻击”或“防守”但攻击之后会积累一个“眩晕值”防守会消耗这个值。那么此时“当前回合是否清醒”这个状态不仅取决于当前的操作还取决于前几回合的操作历史。如果直接把状态定义为“当前回合做什么”DP就失效了因为同一个状态背后隐含的历史不同未来也完全不同。克服方法也很经典把历史中影响未来的因素“吸收”进状态维度里。在这个例子中增加一维“剩余眩晕值”状态变成“当前第几回合、剩余眩晕值”这样一来状态一旦确定未来的决策空间就唯一确定了无后效性恢复。我在第4节讲状态设计时会再深入说这个“吸收历史到状态”的技巧。2.4 一票否决贪心才是更优解的情况有一种情况特别尴尬题目确实具备最优子结构但使用贪心策略就能达到同样效果而且复杂度更低。比如“从一堆硬币里挑选最大面额使总数达到目标”——如果硬币面额满足某些特殊性质贪心即是正确解但大部分情况下是假命题。DP能覆盖贪心能解的部分问题但反过来不行。我的判断技巧是先问自己“每一步做一个当下的最优选择不回头调整结果还会正确吗”如果明显不正确例如经典的找零问题中面额1、3、4要凑6贪心选411用了3枚最优其实是33用了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层的路径只能由第i1层派生分解天然成立。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])但这会让“12”和“21”算成两种方案而题目如果只关心组合不区分顺序这就是错了。要避免这个问题必须加上“当前用到哪一类硬币”这一维度把组合顺序强制排掉。边界值也永远要单独思考状态维度里出现0怎么办比如dp[0][0]初始化为0还是1取决于它的含义是“没有元素时的值”还是“没有元素时的一种空方案”。这类细节是需要结合“最后一步”的递归树从最小情况逐步确定的。4.4 用“示例驱动”检查状态定义是否靠谱状态设计完成之后我建议不要急着写代码。先拿一组很小的输入比如n3或者金额5手工按状态定义推一遍表格看看结果是否符合直觉。这一步耗费的时间很少但能避免大量因状态定义错误而导致的返工。特别是当你发现某个格子的值不符合常识时不要修修补补直接回头审视状态定义。我见过太多人定义错了状态然后在转移方程上疯狂调试两三个小时。相比之下花十分钟用手推一遍小样例就能立刻发现问题。这份“慢思考换快调试”的耐心是DP题做得快的人共同的特点。5. 空间优化的尺度什么时候该滚什么时候别滚空间优化是DP题里最容易被过度追求的一件事。滚动数组、原地修改、状态压缩写出来确实赏心悦目但对于初学者我建议把优先级往后放先把时间和空间都正确的版本写出来再谈优化。不过理解优化的原理本身能反过来加深你对状态依赖关系的认识。5.1 滚动数组的本质只保留“未来还会被参考”的状态滚动数组的出发点是自底向上填表时计算dp[i][:]只需要依赖dp[i-1][:]或更早的固定几行那些已经不会被再参考的旧行完全可以覆盖掉。这样二维表被压缩成了一维或者两维交替使用空间从O(n*m)降到O(m)。一个最典型的例子就是数字三角形。计算第i层时只依赖第i1层所以只需要开一个一维数组从最底层开始每计算完一层就在原数组上覆盖下一层的值方向从前往后即可。这属于“十分安全”的压缩因为旧值用完即丢没有二义性。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时会把从未计算过的状态当成有效值。计数类DPdp[0]通常设为1代表“空方案”而不是0否则从起点出发的所有方案都会变成0。初值问题最好的检验方式是用最小样例手推比如n1或amount0时结果应该等于什么如果手推和代码跑出来的不一致百分之百是初值定义错了不需要继续调试转移方程。7.3 复杂度估算写之前先算一遍表有多大“调试半小时提交超时”这件事根子在于没算复杂度。DP的时间复杂度是“状态数乘以每个状态的转移数”状态数是各个维度规模的乘积。写代码前先估算n1000且m1000那么二维表就是100万个状态每个状态O(1)转移整体O(10^6)Python一秒钟内没问题。但n10^5且状态也要10^5再加O(n)转移就是O(10^10)只有理论意义必须考虑压缩维度或换算法。这种估算能力也是面试中的隐形加分项。你不仅给出解法还顺手分析时间和空间复杂度好坏高下立判。7.4 用“小样例手推”替代“盲目打断点调试”DP题与普通题最大的调试区别是普通题断点看变量一眼就能发现问题DP题表格一旦铺开几百个格子的中间值根本看不过来。我的习惯是开着三个小样例跑每个样例规模不超过5然后把这些样例的表格用手工推一遍和程序输出逐格对比。只要有一个格子不一样顺着依赖往回倒查很快就能定位是转移方程错还是初值错。这个方法的思路是把调试范围压缩到人可以手工验证的尺度。与其在1000x1000的表海里捞针不如在三维小表上精准复核效率高得多。长期坚持这个习惯慢慢地你就不太需要调试了因为你在写代码前的设计阶段已经通过手推样例把所有逻辑验证了一遍。写在最后动态规划是我认为“投入产出比”最高的算法主题之一它不像数据结构那样需要背大量模板也不像图论那样对建模能力要求极高。只要掌握“暴力递归→记忆化→递推→优化”这条路径再用“最后一步”思维反复练习状态设计几乎能覆盖大部分题目。我个人的习惯是每次遇到一道没见过的DP题先写暴力递归再用缓存优化递推版本只是最后“锦上添花”的事。这个顺序可能不如直接照着状态转移方程写代码看起来“快”但它省去了大量试错时间也让我对每道题的理解都深入一层。如果你现在正被动态规划折磨不妨从下一道题目开始试着先把暴力版写出来再画一画递归树你会发现自己对“状态”“转移”这些概念的理解会有一个质的改变。