很多人第一次接触动态规划Dynamic ProgrammingDP时的状态都一样看教程的时候觉得懂了合上电脑自己动手写连状态定义都卡在一个空上。DP难难在一个“想”字——它不像排序、二分那样有固定模板可套每一道题的状态设计、转移方程几乎都是量身定制的。作为系列教程的第4篇这次我打算换个方式不讲那些吓人的数学记号就说一套我自己刷题多年反复在用、也被周围人验证过无数次的拆题方法配合几个经典模型让你看完之后至少能独立上手中等难度的DP题。这篇文章不预设你已经有什么DP基础但希望你手里有基本的递归理解和一段“暴力枚举”的经验因为DP说白了就是有记忆的、聪明的暴力这两样你已经有了接下来的内容就不会吃力。我还会把自顶向下记忆化搜索和自底向上递推两条路线都讲清楚并且给出两者之间如何切换的实操建议。如果你是准备面试、笔试的开发者或者正在补算法短板的在校学生这一篇应该能帮你省不少摸索时间。1. 为什么要动态规划先搞懂它解决的到底是什么问题1.1 从一段会超时的递归说起我要用的第一个例子极简单就是人人见过的斐波那契数列。递归写法大家都会写def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这段代码逻辑完全正确但n只要稍微大一点运行时间立刻变得不可接受。原因出在调用关系上计算 fib(5) 要分别调用 fib(4) 和 fib(3)计算 fib(4) 又要调用 fib(3) 和 fib(2)。你看fib(3) 被算了两遍fib(2) 更是被重复算了好几遍。当 n40 的时候这个函数大概要执行几千万次调用等 n50等待时间就已经是以分钟为单位了。同一个参数对应的子结果完全相同却在递归树里被反反复复地重新计算这就是所谓的重叠子问题。任何天然递归都可能踩进这个陷阱而动态规划要解决的核心问题就是把这次浪费彻底去掉。理解了这个动机再看后面的优化手段就一点都不神秘子问题既然会重复出现那我把它算完一次之后“存起来”下次直接取结果不就行了。1.2 最优子结构与重叠子问题DP成立的基石DP不是万能的一道题能用DP求解必须同时满足两个性质重叠子问题。大问题拆出来的小问题会被反复使用。如果没有这个性质每个子问题只算一次也就没有任何“记忆化”的必要了。最优子结构。大问题的最优解可以由子问题的最优解直接推导出来。经典例子是求从城市A到城市C的最短路径如果最优路径经过中间点B那么从A到B这一段一定也是A到B的最短路径否则用一条更短的A到B路径替换上去整体还能更短这就产生了矛盾。这两个条件缺一不可但它们其实非常符合直觉。所以我在看到一道新题时不会急着写代码而是先问自己三个问题这个问题能拆成子问题吗子问题之间重叠吗大问题的最优解里是不是藏着子问题的最优解如果三个回答都是“是”基本可以放心上DP了。这也是为什么很多前辈说DP是“聪明的暴力枚举”暴力的本质是把所有方案都试一遍DP也会把每个子状态老老实实算一遍但它通过记住中间结果避免了对同一状态做无意义的重复计算从而把很多指数级复杂度的搜索压成了多项式级。2. 动态规划的两条实现路线记忆化搜索与自底向上递推实现DP有两个主流方向方法不同但解决的是同一个问题。两条路我都会讲因为我发现不同人的思维方式完全不同有人喜欢从大往小拆有人喜欢从小往大攒没有高下之分。2.1 记忆化搜索最符合直觉的写法记忆化搜索就是“递归 缓存”。刚才那个斐波那契递归最朴素的版本不记忆那我们就给它加一个字典算之前先查算过就直接返回def fib_memo(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 1: return n memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo) return memo[n]核心逻辑就一句话算过就返回没算过才往下递归。这样每个 n 只计算一次时间复杂度从指数级降到线性空间复杂度 O(n)。记忆化搜索的最大优势是贴近人类自然思维你先按递归的思路把“当前问题答案 子问题答案的组合”写出来再顺手加个缓存完事了。对于刚接触DP的新手这是最不容易出错的路线也是我强烈建议你第一遍“求正确性”时优先使用的办法。2.2 自底向上递推最稳、最可控的写法自底向上则完全不使用递归直接开一个数组从小到大填格子def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[0], dp[1] 0, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这种写法就是大多数人嘴里的“纯DP”。它的优势在于一旦状态定义清楚、循环顺序正确代码的执行路径非常直观不用关心递归调用栈深度运行开销也更小。缺点是需要一点抽象能力你得先想明白“从底到顶”的填充顺序。这里有一个容易让新手混乱的点很多人以为“自底向上”里的“底”是指数组下标 0其实不是它指的是子问题规模从小到大的方向。规模最小的子问题往往就是初始条件然后逐渐推导到规模最大的原问题。2.3 两条路线到底怎么选我的实际经验是这样做题、面试当场如果状态维度比较少一维或二维并且转移关系是“当前格子由前几个格子组合而来”用自底向上更稳因为递推顺序可控后续做空间优化也方便。如果题目带明显的搜索味道比如带条件分支、回溯、博弈轮次或者一开始根本递推方向想不清楚那就果断先写记忆化搜索至少能在短时间内拿到正确答案。还有一招我经常用先用记忆化搜索把正确解法拿到手再花几分钟把它翻译成自底向上的递推。这样既保留了“容易想对”的优点也拿到了“容易优化”的最终版本。记住面试官最后要看的通常是你能不能在纸上写出一个干净的迭代DP但你需要的是先有一个绝对可信的正确版本做参照。3. 设计DP的“四步法”每一步都有明确产出很多人把DP当成“灵感题”觉得想到了就秒杀想不到就是脑子不够用。其实DP有相当强的结构化流程我把它总结成固定的四步每一步都追问自己一个具体问题卡壳概率会大幅下降。3.1 第一步用一句话把状态定义讲清楚状态定义是整个DP的基石。我发现很多人写不出转移方程根本原因不是不会转移而是状态定义本身是模糊的。我给自己定的规矩是必须能用一句“dp[下标参数] 在该参数条件下问题的答案”把状态说清楚说不清楚就继续想。斐波那契dp[i] 表示数列第 i 项的值。最长递增子序列dp[i] 表示以第 i 个元素为结尾的最长递增子序列长度。背包问题dp[i][w] 表示前 i 个物品里选一些背包剩余容量恰好为 w 时能获取的最大价值。状态定义的核心原则是把影响后续决策的所有关键信息都塞进下标里。如果问题里有“剩余步数”“当前容量”“已用次数”这类硬约束它们通常都要变成状态的一维。漏维度是新手最容易犯的错误一旦漏了后面怎么写都不对。3.2 第二步用“最后一步”倒推转移方程有了清晰的状态定义下一步就是描述状态之间的关系。我用一个百试不爽的思考方式问我当前问题“关闭最后一件决策”是什么。具体说就是假设我已经知道了所有规模更小的子问题答案那么我要怎么把它们的答案组合成当前问题的答案。斐波那契第 i 项就是前两项之和得到 dp[i] dp[i-1] dp[i-2]。编辑距离我盯住两个字符串的最后一个字符认为所有可能的“对齐方式”一共有三类删除、插入、替换取它们的最小值加一。这一步最大的坑是急着“一步到位写终极公式”。我的建议是先写一个口语版的逻辑描述比如“当前格子的值 min(左边格子1, 上边格子1, 左上角格子替换代价)”然后再翻译成代码。先有逻辑后有公式一旦代码写错你也知道是逻辑偏差还是笔误。3.3 第三步把初始条件说死边界划清转移方程是从已知推未知那么这个链条的起点、那些无论如何都无法再分解的最小规模子问题就是初始条件。斐波那契的 dp[0]0、dp[1]1 是初始条件LIS 的 dp[i]1 是初始条件编辑距离的第一行 dp[0][j]j、第一列 dp[i][0]i 也是初始条件。边界的难点通常在于防止越界。我的习惯是两招并行第一把 dp 数组开大一点多留几个哨兵格子第二在下标访问前统一做偏移或加保护判断。但你要清楚扩容的格子只是“方便编码”的工具真正的状态语义一定还是原本的含义。千万别为了好写代码而把状态定义改乱那是捡芝麻丢西瓜。3.4 第四步画依赖箭头定遍历顺序遍历顺序是自底向上DP里最容易被忽视、但一出错就全军覆没的点。判断标准只有一条当前状态需要用到的所有子状态必须在计算当前状态之前已经算出来。拿斐波那契说算 dp[3] 需要 dp[2] 和 dp[1]所以从 dp[2] 开始从小到大遍历没问题。二维情况下转移方程可能同时引用 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]看到这类依赖你应该立刻意识到外层循环 i 从小到大内层循环 j 从小到大这样左上角、正上方、正左方的格子都已经算好了。如果遇到依赖方向不同的题目就把方向反过来。我强烈建议你真的在纸上画一张3x3的表格用箭头把每个格子的依赖标出来箭头方向一眼就能看出遍历顺序比死记硬背强一百倍。注意遍历顺序不是“随缘”的也不是“默认从零开始”就完事了。每次写完DP我都会专门问自己一句当前格子的依赖格子算出来了吗如果没算出来那这个遍历方向一定有问题。这一步是二维DP里最常踩的坑没有之一。4. 经典模型拆解三道递进的门光讲理论永远学不会DP必须上手做一些经典的题目模型。下面这三个模型难度递增把它们的推导过程吃透你以后看到大量中等DP题至少能认出“原型”解题速度会快很多。4.1 0-1背包所有“选还是不选”问题的鼻祖0-1背包问题描述有 n 个物品第 i 个物品重 w[i]、价值 v[i]背包总容量为 C每个物品最多拿一件问能带走的最大价值是多少。状态定义dp[i][c] 表示从前 i 个物品中选在总容量不超过 c 的前提下能获得的最大价值。转移的核心是讨论第 i 个物品“拿还是不拿”不拿延续前 i-1 个物品在容量 c 下的最佳结果即 dp[i-1][c]拿前提是 c 足够装下第 i 件物品即 c w[i]那么容量先扣掉 w[i]价值加上 v[i]后续还能从前 i-1 个物品中继续选即 dp[i-1][c - w[i]] v[i]。所以转移方程写成if c w[i]: dp[i][c] dp[i-1][c] else: dp[i][c] max(dp[i-1][c], dp[i-1][c - w[i]] v[i])这个模型的价值绝不止于背包本身。它是一种“决策序列”的通用抽象从候选集合里挑一部分出来配上资源约束求某个目标的最值。项目排期里选任务做、预算里挑项目投、甚至点菜预算内选最爽的搭配本质都是背包。学会这一道等于解锁了一大类优化题的口子。4.2 最长递增子序列状态定义方式的经典示范问题给定一个数组 nums求最长严格递增子序列的长度。注意子序列不要求连续但必须保持元素间的相对顺序。这道题最重要的启发就在于状态定义dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。为什么非得用“以 i 结尾”来定义因为这样转移才优雅对于任意 j i 且 nums[j] nums[i]都可以把 nums[i] 接到以 nums[j] 结尾的递增子序列后面形成一个新的、更长的递增子序列长度为 dp[j] 1。对所有满足条件的 j 取最大值就得到 dp[i]。dp [1] * n # 每个元素单独本身就是长度1的子序列 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) answer max(dp) # 这才是真正的答案顺带一提最终答案必须取整个 dp 数组的最大值而不是 dp[n-1]。因为以最后一个元素结尾的递增子序列不一定是最长的这是一个高频易错点。这个模型也打开了“以某某结尾”这种状态定义思路的大门后面的最长公共子序列、编辑距离、最大子序和全都在用同一招。4.3 编辑距离二维DP的启蒙关卡编辑距离问题是字符串DP里很经典的二维状态模型。问题给定两个字符串 s 和 t一次操作可以插入一个字符、删除一个字符、替换一个字符问把 s 变成 t 最少需要多少次操作。状态定义dp[i][j] 表示 s 的前 i 个字符变成 t 的前 j 个字符所需的最小操作数。我在纸上画表格时习惯在第一行和第一列分别标示空串到各前缀的转换成本这样看格子的时候特别直观。推导转移方程时核心还是“看最后一步做了什么”。如果 s 的第 i 个字符和 t 的第 j 个字符相等那这两个字符天然对齐代价直接继承 dp[i-1][j-1]。如果不相等就有三种操作方向删除 s 第 i 个字符代价 dp[i-1][j] 1在 s 末尾插入一个字符去匹配 t[j]代价 dp[i][j-1] 1把 s 第 i 个字符替换成 t[j]代价 dp[i-1][j-1] 1。最终转移方程if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1初始条件也很有推敲价值dp[0][j] j 表示空串变成 t 的前 j 个字符只能靠插入dp[i][0] i 表示 s 的前 i 个字符变成空串只能靠删除。我当时是拿 shorse、tros把整张 6×4 的表格一格格亲手填了不下五遍才算真正理解了二维DP是怎么“由已知推未知”的。这个功夫不建议省因为字符串类DP的套路基本都从这里发芽。5. 空间优化从二维数组到滚动数组怎么压才不出错5.1 为什么说“能够压维”本身是一种洞察很多DP题的状态是二维的但你盯住转移方程看就会发现dp[i][c] 只依赖 dp[i-1][...]也就是说当前行只与上一行有关跟更早的行完全没有关系。既然如此我们为什么还要把整张 n×m 的大表都保留下来保留“当前行的数据”和“上一行的数据”就足够了上一行算完就扔掉新一行直接在原数组上滚动覆盖这就是滚动数组的由来。但“滚动”有一个致命的细节以 0-1 背包的一维优化为例外层循环遍历物品内层循环遍历容量时必须倒序。为什么因为 dp[c-w[i]] 这个子结果不能被本轮已经更新过的新值覆盖。如果正序遍历容量小的格子先被本物品更新后面容量大的格子再用 dp[c-w[i]] 时拿到的是“已经包含本物品”的旧值于是本次迭代等于把一个物品用了多次——0-1背包活活变成了完全背包结果必然偏大。5.2 滚动数组的正确打开方式我强烈建议你遵循这个顺序先老老实实写二维版本确认正确再做压维优化。一上来就写一维一旦出错你根本分不清是转移方程错了还是优化过程引入的新bug调试成本会非常高。二维版本写好之后画出依赖关系图问自己两个问题当前格子的数据来自哪个方向那个方向的数据会不会被本轮的更新覆盖如果会就把循环方向反过来。还有一个自查办法把压维后的循环逻辑翻译回二维表格模拟几次手动填充如果发现“用本行数据覆盖了上一行需要的数据”遍历方向就得改。压维之后还有一个额外收益很多在线测评系统极限数据下二维数组会内存超限一维滚动数组直接就把内存降了一个量级。所以这道工序不只是“花活”是实打实的硬需求。6. 动态规划、贪心、分治三条容易走岔的路6.1 分界线到底画在哪里初学者最容易把贪心和DP混在一起因为它们都在“拆小问题、逐步推进”。但它们的本质区别非常明确分治子问题互相独立。归并排序把数组劈成两半两半的排序互不影响结果直接合并不存在“重复子问题”也因此不需要记忆化。贪心每一步都做“当前看来最好的选择”并且绝不回头。但贪心成立是有前提的——需要证明局部最优能累积成全局最优否则它只是一个“大概率能拿分”的冒险策略。DP把所有子问题都算出来在依赖关系里做全局最优的取最大、取最小。它不追求每一步局部最优而是保证每一步结束时该状态下所有可能的决策历史都被留住了。6.2 用找零问题看清贪心的边界举个例子硬币面额为 1、5、11要找 15 块钱。贪心策略会优先拿最大面额于是 11、1、1、1、1共 5 枚。但最优其实是 5、5、5共 3 枚。这就说明贪心的局部最优选择先拿大额在后续会导致更差的累积结果这个场景就不能用贪心只能靠DP把面额组合当成状态空间来搜索。我还想强调一点DP的本质其实就是“带记忆化的搜索”。搜索树上的每个节点对应一个子问题记忆化把重复子树全部剪掉。理解了这个底层关系你就明白为什么有些DP题想不通时可以先写一个低效的暴力搜索再逐步加缓存、改状态最后优化成真正的DP。这个“暴力→剪枝→记忆化→迭代DP”的进化路径是我个人觉得学习DP最省力的一条主线。7. 调试与避坑DP不是想出来的是“看”出来的7.1 打印DP表最朴素也最高效的调试法我在平台刷题时经常看到有人对着代码发愁却不知道从哪下手。我的办法非常土把 dp 表打印出来。但不是只打印最终答案而是把整张表或者关键的几行几列原原本本打出来肉眼检查。以编辑距离为例打印整张二维表之后先检查第一行是不是 0,1,2,3...第一列是不是 0,1,2,3...再随机挑一个格子用自己的直觉判断“把 s[:i] 变成 t[:j] 的最小操作数”是不是这个数。如果中间某个格子突然出现一个反常识的大数字那基本可以锁定是初始化、转移条件或边界处理的问题。这个方法另一个好处是面试时可以直接把表画给面试官看沟通效率远比盯着代码解释高得多。7.2 高频错误速查表错误类型典型表现排查思路状态定义含糊转移方程写不出来回到定义层问“影响当前决策的信息有哪些”初始化错误前几行结果与手算不符手动用小数据填一遍前几行比对期望值边界越界运行时报数组越界统一加偏移或用哨兵格子规避再验证边界格子遍历顺序错误结果随机或明显偏大画依赖箭头图保证先算完依赖项状态维度缺失结果永远差一点重新读题检查是否漏了“容量/次数/步数”等约束压维后才出错一维结果明显不符退回二维版本确认二维逻辑无误后再压维经验如果我在一道DP题上连续错三次以上大概率不是代码写错而是状态定义或转移方程本身有漏洞。这时候继续改代码没有任何意义正确做法是停下来重新画表、重新推导把问题想明白再动手。Debug DP题多在纸上花时间反而比在编辑器里花时间更快。8. 最后再分享一点自己走过的弯路动态规划不是一个能速成的知识点它更像一门手艺。我第一次真正“开窍”是在某次闭关刷题时用手工把一道二维DP的整张表格填了三遍填到第三遍的时候突然意识到原来每一个格子背后就是一段被我们“记住”的决策路径。之后再看任何DP题心态都完全不一样了。如果你现在正卡在“看得懂、写不出”的阶段我的建议是不要硬刷题量。优先保证斐波那契、上楼梯这类一维题能独立写出来然后手工推导一遍LIS和编辑距离最后再把背包的滚动数组优化亲手实现一遍。每一步都要动手填一次 dp 表别光看别人的解析。这些基础模型走完之后再遇到树形DP、状压DP这些进阶玩法你至少不会连切入点都找不到。剩下的就交给时间和持续的刻意练习了。