1. 动态规划不是玄学先从这层窗户纸说起我最早学动态规划的时候跟很多人一样觉得它是算法森林里最神神叨叨的那棵树。背了状态、转移、边界几个词看了十几篇教程遇到新题照样懵。直到后来刷了几百道DP题又回头把最基础的爬楼梯、斐波那契给重新推导了一遍才明白这层窗户纸到底在哪。先说结论动态规划本质上就是把暴力枚举里的重复计算缓存起来同时把一个大问题拆成层层递进的子问题。它不玄它只是把怎么拆、怎么递、怎么合这三件事给规范化了。你之所以觉得它难是因为很多教程直接扔给你一个状态转移方程却不说这个方程是怎么从暴力解里长出来的。本文会从暴力递归开始一步步带你长出一个DP解再配几类高频模型的识别方法和完整实战案例最后聊聊我在刷题过程中踩过的一些坑。这篇文章适合什么基础的人如果你会写循环和递归但见到DP题没有稳定的思考套路可以放心往下看。我会尽量把一个模型对应一类题的思考过程讲完整而不是只给方程。1.1 用现实场景理解最优子结构动态规划有个前置概念叫最优子结构解释起来很绕但现实中到处都是。你要从A地坐车到D地中途经过B、C那么全程最优路线里从B到D那一段必然也是从B到D的最优路线。为什么如果存在一条从B到D更短的路那你把A到B那段接上全程会更短这就矛盾了。这个矛盾论证就是最优子结构的严格证明思路。算法题里最长递增子序列、背包问题、编辑距离都是典型的最优子结构。做题时判断一个题能不能用DP最粗糙也最有效的初筛方法就是如果你已经知道前i个元素的最优值能不能只用它或者它加上当前元素的信息推出前i1个元素的最优值如果能大概率可以DP如果必须回溯到很深的过去才知道当前结果那DP就不太合适。1.2 状态、转移、边界DP的三个零件这三个词听起来像八股但其实是把拆问题的过程标准化。状态就是我现在描述到哪个位置了转移就是从已知状态到当前状态怎么算边界就是最初始的那几个位置怎么定。三者缺一不可而且顺序有讲究。我的习惯是先定状态再写暴力递归然后根据递归函数里的分支确定转移最后用肉眼检查递归出口对应边界。很多人反过来先背转移方程再硬凑状态这最容易翻车。状态定得对不对是DP题唯一真正的难点后面的转移反而是体力活。三个零件分别对应代码里的什么状态是一个数组的维度转移是数组里某个格子怎么由之前的格子算出来边界是数组初始化时填的第0行、第0列。后面实战部分我会用零钱兑换把这个映射关系演示一遍你会发现一旦代码和概念对上了理解就落地了。1.3 重叠子问题为什么DP能比暴力快那么多暴力递归慢是因为同样的子问题被算了无数次。以斐波那契为例递归算fib(5)要算两遍fib(3)、三遍fib(2)数字一大计算量指数爆炸。DP的想法很简单每个子问题只算一遍存进表里下次用的时候直接拿。很多教程把重叠子问题和最优子结构并列当DP的两大条件但我的理解是只要具备最优子结构子问题本身就一定存在重叠——只是重叠程度有大有小。DP的缓存策略就是把重叠部分压成一份。所以你在做题时如果暴力递归写出来总觉得重复计算很厉害基本可以确认这题该用DP或记忆化搜索来优化。2. 别急着写DP从暴力递归到状态缓存的自然推导我发现一个规律能顺畅写出DP解的人几乎都能先写出正确的暴力递归。反过来一上来就抄转移方程的人换个马甲就不会了。所以这一节我带你把推导过程完整走一遍用斐波那契当最简单的例子体验一条可复用的生产线。2.1 第一步先写一个正确但很慢的递归先不管性能先保证逻辑正确。斐波那契的递归是这样def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个代码最大优点是完全忠实于数学定义不会错。它的调用树里每个节点都是同一个子问题在不同路径下的重复展开比如fib(3)被算了多次。我们来推一下如果n30调用次数大概是百万级别n40就是上亿级别肉眼可见卡顿。题外话我自己写暴力递归的时候有个习惯参数能少就少。参数越少后面转换DP时状态维度就越简单。如果暴力递归带着四五个参数通常意味着你还没有把冗余信息压缩干净。2.2 第二步加一个缓存改成记忆化搜索递归慢的唯一原因是重复算那就加个dict或数组缓存住结果这就是记忆化搜索。memo {0: 0, 1: 1} def fib_memo(n): if n in memo: return memo[n] memo[n] fib_memo(n - 1) fib_memo(n - 2) return memo[n]这步非常关键因为它验证了一件事状态定义和递归思路是同一个东西。memo的key就是状态递归函数体里的分支就是转移方向。你甚至不用重新设计直接给暴力递归加缓存性能就已经接近DP了。面试时如果一时想不出递推的DP写法先写记忆化搜索也是稳妥方案大部分面试官会认可之后再聊优化空间即可。2.3 第三步把递归翻成自底向上的递推记忆化搜索仍然是递归有函数调用开销也可能栈溢出。改成递推就是把从上往下拆翻成从下往上算。斐波那契版本def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]到这里三个零件全齐状态是dp[i]转移是dp[i] dp[i-1] dp[i-2]边界是dp[0]0、dp[1]1。你可以把这份代码和暴力递归放在一起看会发现递推其实就是把递归画成图之后按拓扑排序的顺序从起点一路走到终点。2.4 小样例手算调试DP唯一可靠的方式很多人DP写错了不知道怎么查其实有个朴实的办法拿n5这种小样例把dp数组每一步变化手写出来和代码跑的结果对比。我在白板上画过几千个数毫不夸张这是排查DP问题最稳定的手段。具体做法是先头脑里执行一遍转移在纸上列出dp[0]到dp[5]的每一格数值然后跑代码加一行print看实际输出。不一致时要么手动推错了要么代码写错了。别猜把两边对齐错误一定会暴露在第一个差异点上。这个方法够笨但DP题的bug十有八九是这么抓出来的。3. 高频DP模型的识别与突破口线性、区间、背包、树形动态规划的题目表面千变万化但骨架就那么几副。我会把每个模型的识别特征和常规状态定义讲清楚相当于给你一张地图。你要做的不是背地图而是在刷题时反复对照慢慢形成肌肉记忆。3.1 线性DP数组和字符串题里的常客线性DP的识别特征特别明显输入是数组或字符串状态通常是一维的从左往右推。新手第一个接触的这类题基本是最长递增子序列。它的状态定义是dp[i]表示以nums[i]结尾的最长递增子序列长度转移是往前面找比nums[i]小的元素取最大值加一for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1)这个模型覆盖了不少题打家劫舍、不同路径、跳跃游戏II等。识别出从左往右推一个一维数组这个共性后再遇到类似结构心里就有底了。需要提醒的是线性DP不一定只有一维比如编辑距离、最长公共子序列需要二维状态但推进方向依然是从左到右或者从上到下思维模式完全一致。3.2 区间DP操作对象是一段连续范围区间DP一个很显眼的特征是最终答案对应的是整个区间的最优解而且计算过程中子问题是子区间。经典题莫过于合并石子和最长回文子序列。状态一般是dp[i][j]表示区间[i, j]的答案转移时用区间长度做外层循环从小到大枚举长度再枚举起点和分割点。我最早学区间DP时犯过一个错误直接用i从小到大的顺序来算dp[i][j]结果发现自己依赖的dp[i1][j-1]还没算出来。后来明白区间DP的循环顺序不是按左端点而是按区间长度。先算长度为1的所有区间再算长度为2的所有区间以此类推转移时依赖的永远是更短区间。这个长度外层循环是区间DP最容易翻车的地方我在第5节还会专门展开讲。3.3 背包类DP价值、容量、选取策略的三件套背包问题的识别不用多说了多个物品每个有体积和价值背包容量有限问最大价值。状态天然是二维dp[i][j]表示前i个物品放进容量j的背包能获得的最大价值。0/1背包的转移是dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1])完全背包只是把选或不选当前物品改成选几个当前物品代码上最直观的差异是内层循环的方向不一样。很多人只背这个方向结论却不理解为什么——0/1背包从右往左遍历容量是为了保证每个物品最多被选一次完全背包从左往右遍历是因为同一件物品可以被反复使用。这个遍历方向决定语义的细节后面我也要重点讲。3.4 树形DP与状压DP什么时候值得用树形DP识别起来也简单输入是树结构答案通常和每个节点及其子树有关。典型题如打家劫舍III状态是dp[node][0/1]表示节点选或不选时子树的最大值转移时把所有子节点按规则合并到父节点。这类题需要先对树做DFS用递归从叶子一路推到根。状压DP稍微进阶一些特征是数据范围非常小通常n不超过16或20因为要用二进制整数表示一个集合。比如旅行商问题的状态dp[mask][i]表示已访问集合为mask、当前在节点i的最短路径。这类题我建议初学者等前三种模型都熟练掌握后再碰原因是状压DP的代码短但思路抽象状态转移容易写成晦涩的位运算不具备一定基础很容易劝退。4. 完整实战拆解零钱兑换从读题到AC全过程光讲模型不练题等于看菜谱不下厨。我挑一道非常典型的题——零钱兑换带你走一遍完整的思考流水线。题目是给定不同面额的硬币coins和一个总金额amount求凑成该金额需要的最少硬币个数如果凑不够返回-1。这道题在LeetCode上是322题面试出现频率极高。4.1 先想清楚为什么贪心在这里失效拿到题第一反应可能是贪心从大面额开始尽量用大钱用的硬币不就少了吗但coins [1, 3, 4], amount 6时贪心先取4剩2再取1和1总共3枚。而正确答案是两枚3。这就是典型的局部最优不等于全局最优所以必须用DP或BFS。我提这一点是想强调看到最少/最多/最短这类词先别急着贪心先想想局部最优会不会坑全局如果会就该考虑DP。4.2 状态定义是怎么出来的按照我的习惯先写暴力递归。递归函数f(amount)表示凑出amount最少需要多少枚硬币。为什么只带一个参数因为所有硬币都是可重复使用的所以状态里不需要前i种硬币的维度。那么f(amount)的转移怎么来凑出amount要么最后一枚是c1要么是c2要么是c3。如果最后一枚是coin c那之前的任务是f(amount - c)。所以f(amount) min(f(amount - c) 1 for c in coins)边界是f(0) 0如果amount小于0说明上一枚选得不合适返回无穷大。到了这一步递推代码几乎可以直接翻译了dp[i]表示凑出金额i最少需要的硬币数dp[i] min(dp[i-c] 1)。这套推导过程充分说明暴力递归真的不是弯路它是通往可靠状态定义的最捷径。4.3 初始化用大数无穷大要选得聪明dp数组长度是amount1dp[0] 0其余初始化为一个很大的数。为什么不能初始化为0因为如果初始化为0转移时min(dp[i], dp[i-c]1)计算出来的永远是1直接破功。我用过几种无穷大float(inf)方便但不推荐因为后面min计算时会把整数和浮点数混在一起打印时也不好看。我通常初始化成amount1因为在最坏情况下全部用1元硬币硬币数最多是amount所以amount1是一个安全而明确的不可能达到的上界。同样的逻辑在很多题里成立求最长/最大时初始化成0或负数求最短/最小时初始化成一个大数。这个大数的取值需要根据题目上界来估算不能拍脑袋。4.4 计算顺序与完整代码dp[i]依赖的是dp[i-c]而i-c必然小于i所以从小到大遍历金额i每个i遍历所有硬币c即可。完整实现def coinChange(coins, amount): dp [amount 1] * (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] ! amount 1 else -1代码就这十几行但背后的推理链条远比代码本身重要。我建议你写完这篇以后把上面的推导过程也记在题解旁边为什么状态只带金额不带硬币种类为什么初始化是amount1为什么内层遍历方向无所谓以后回看时你会比刷十道新题都收获大。4.5 边界用例测试清单提交前我习惯过一遍边界amount为0时直接返回0因为一个硬币都不用coins里最小的面额大于amount时dp全程保持amount1最终返回-1amount很大时注意dp数组会不会内存爆掉如果amount是10^9那说明这题根本不能用这种裸DP得换思路比如用BFS或货币种类数做状态。边界测试不是走形式很多隐性bug都在这些地方。5. 刷DP题一年我总结出的四类高频坑这部分是纯经验分享每一条都来自我自己或带人刷题时真实踩过的坑。你如果以后遇到类似问题可以回来对着排查能省很多时间。5.1 状态定义的维度缺失为什么改来改去都不对最隐蔽的坑是状态维度缺失。比如打家劫舍如果你只看前i个房子偷多少会不知道第i-1个房子有没有被偷因为相邻限制要求你不能偷相邻的两个所以状态必须加一维dp[i][0]表示前i个房子且第i个不偷的最大值dp[i][1]表示第i个偷。这个维度缺失时你写出来的转移总像隔靴搔痒答案也有模有样地错着。怎么判断状态缺维拿暴力递归的参数来对照。递归函数有几个参数dp通常就要有几维。如果你在递归里依赖某个历史信息而这个信息没有被放进参数里那就是维度缺失的信号。先补参数再补维度思路立刻亮堂。5.2 初始化和返回值搞错边界就是一堆特判初始化上面讲过这里补充一个返回值陷阱dp[m][n]是不是最终答案取决于你的状态定义。有时候正确答案是max(dp[i])有时是dp[n]本身有时候是dp[m][n]。我犯过的错误是机械地认为最后一个格子就是答案结果在最长递增子序列题里答案其实是整个dp数组的最大值因为最长递增子序列不一定以最后一个元素结尾。判断标准很简单回到状态定义问自己我最终要的全局最优对应的是哪个状态如果状态表示的是以某个位置结尾的子问题答案是全局max如果状态表示的是处理到某个位置为止的全局问题答案就是最后一个状态。一字之差决定生死真不是夸张。5.3 循环方向0/1背包为什么要从右往左遍历容量0/1背包的经典代码里容量那一维要倒着遍历for i in range(1, n 1): for j in range(target, weight[i-1] - 1, -1): dp[j] max(dp[j], dp[j - weight[i-1]] value[i-1])如果是完全背包内层循环就改成正向。这个差异的原因我举个例子你能立刻明白假设只有一个物品重量为1价值为5target为2。如果正向遍历dp[1] 5dp[2] max(dp[2], dp[1] 5) 10相当于同一个物品用了两次这正是完全背包想要的但如果题目是0/1背包这就错了。倒着遍历时dp[2]依赖的是上一轮还没被当前物品污染的dp[1]天然防止了重复使用。所以方向不是技巧是语义。做题时先想清楚这个物品能不能重复选再决定方向。5.4 空间优化的时机滚动数组不是免费的午餐很多人学DP没几天就上手滚动数组觉得省内存等于秀操作。我坦白说在你对转移依赖关系还不熟的阶段滚动数组只会帮你制造混乱。原因很简单滚动数组会把旧值覆盖掉一旦你还没用完旧值就被覆盖整个转移就崩了。比如区间DP如果你硬要滚动得处理很多复杂情况新手几乎必错。我的建议是先把完整二维数组写对AC以后再考虑优化。优化前问自己三个问题当前状态依赖哪些历史状态那些历史状态是否只被用到一次被覆盖的顺序会不会影响后续计算三个问题都能回答了再动手优化不迟。面试时大多数情况下给出一个空间O(nm)、时间O(nm)的干净解法已经够用刻意秀滚动数组反而容易卡在细节上。6. 我的练习路线与刷题建议按阶段递进不搞题海战术最后聊聊我自己的学习路线不谈必须刷500题这种压力话只说我验证过比较有效的推进方式。你完全可以参考这个节奏根据自己的时间调整。6.1 入门期三类题磨一个月不贪多入门阶段最忌讳只扫一眼题解觉得自己会了就匆匆下一题。我建议把线性DP、背包、区间DP各挑十道左右的经典题认真做到能不看答案手写状态定义和转移推导为止。这阶段慢一点是正常的我在最长递增子序列上卡了整整一周后来发现是自己没掌握以i结尾这种思路而不是智商问题。每道题我都建议在纸上回答三个问题状态是什么转移为什么这么写边界为什么初始化成这个值答不上来就回去翻暴力递归版本。用这个标准一个月刷三十道比三个月刷三百道不思考要有用得多。6.2 进阶期刻意练习识别模型而不是回忆代码到了进阶阶段刷题的目的从会做变成一看题就知道属于哪一类。我的做法是在每道题的题解末尾标注它属于哪类模型、和哪道题相似、差别在哪里。比如零钱兑换本质是完全背包的变种打家劫舍是带约束的线性DP最长公共子序列把两个字符串的维度都拉出来。刻意练习识别能力还有一种高效方法随机抽十道题只做动口不动手每道题讲清楚我会怎么定义状态、怎么写转移、需要几维。讲不出来的题就是弱点回去补。这个过程像在给自己做假面模拟面试对实际面试的帮助极大。6.3 面试与竞赛前的快速复盘策略考前我把笔记整理成一张表模型、识别特征、状态定义模板、边界要点、常见变体每种模型两三行字。这张表就是我的面试宝典。考前一周每天过一遍比临时刷新题管用得多。这张表我不会贴出来替你做因为自己做一遍才是真正内化。动态规划的学习曲线是先缓后陡再平入门期缓慢中间某个点突然豁然开朗之后就是大量重复中找变式。我记得自己在某天刷完一道完全平方数的题后突然有一种所有最值类问题都能用同一套框架去思考的感觉。那个时刻所有这些模型之间的墙就消失了。如果你也走到了那一天欢迎再回头看这篇文章你大概会有不一样的收获。