动态规划这块硬骨头我说是算法面试和竞赛里最容易被卡住的一关应该没人反对。很多人看了几篇教程记住了“状态转移方程”五个字可真拿到一道新题还是懵。原因很简单动态规划不是背模板就能会的它靠的是对“状态”的理解和建模能力。这篇东西我打算用实战经验来讲透它不讲空洞的理论直接用代码和例子把DP的模型、套路、常见坑全部过一遍。无论你是准备算法工程师面试、刷洛谷动态规划题单、还是备战蓝桥杯下面这套思路都适用建议先收藏再慢慢啃。1. 动态规划到底是什么从暴力搜索到状态缓存动态规划被很多人当成洪水猛兽本质上它就是一件事把一个大问题拆成互相重叠的小问题用小问题的答案推出大问题的答案。拆完之后已经算过的小结果存起来后面直接用不再重复算。这个特点决定了它和暴力枚举算法的关系——暴力枚举是硬算每一遍DP是“算一次记下来终身受用”。1.1 万事先从斐波那契说起我先拿最经典的斐波那契数列开刀。要求第n项很多新手第一反应是递归def fib(n): if n 1: return n return fib(n-1) fib(n-2)这么写逻辑完全对但效率惨不忍睹。假设n40这个递归会产生超过一亿次调用因为f(3)这种中间结果被反复算了几十万次。我当年第一次跑这个函数的时候电脑直接卡到风扇狂转。加一个字典做记忆化也就是自顶向下的DPmemo {0: 0, 1: 1} def fib_memo(n): if n not in memo: memo[n] fib_memo(n-1) fib_memo(n-2) return memo[n]这回n1000都秒出。再把递归改成循环从底往上推自底向上的DP连递归栈都省了def fib_dp(n): a, b 0, 1 for _ in range(n): a, b b, a b return a三段代码解决的是同一个问题但背后是从“暴力枚举”到“记忆化搜索”再到“严格动态规划”的进化路径。注意看第三段代码a和b就是状态每一次循环都在做状态转移。这就是DP的骨架。1.2 DP问题的三个特征讲理论之前先给结论一道题能用DP解通常得同时满足三个条件。第一是最优子结构。大问题的最优解可以由子问题的最优解组合出来。比如爬楼梯走到第n级台阶的方法数等于走到第n-1级的方法数加上走到第n-2级的方法数因为最后一步只能跨一级或两级。第二是重叠子问题。子问题被反复计算才有“存下来”的意义。斐波那契的递归树里f(3)被算了无数次这就是重叠。第三是无后效性。某个状态一旦确定后续怎么走跟“怎么走到这里”的历史无关。用白话说只看当前状态不关心来路。比如背包问题里你只关心当前装了多重、总价值多少而不需要知道每件物品具体按什么顺序放进去。这三条可能听起来抽象实际操作时我会反过来检查我的状态定义是否包含了决策所需的全部信息转移时是否只依赖前面已知的状态如果答案都是肯定的那这个DP模型基本立得住。1.3 和分治、贪心的区别很多初学者分不清楚DP跟分治算法、贪心算法的界限。我用一张表来对照对比项动态规划分治算法贪心算法子问题关系重叠结果可复用相互独立不回溯只管当前最优决策方式考虑所有可选方案递归划分逐层合并每步选局部最优典型问题背包、LCS、石子合并归并排序、快速排序、最大子段和活动选择、哈夫曼编码、最小生成树分治和DP最本质的区别就在子问题是否重叠。归并排序把数组一分为二左半边和右半边之间没有共享的子问题所以不需要缓存。贪心则根本不看未来选了就不回头。DP会把所有可能的转移都比较一遍再选最优所以能拿到全局最优解代价是时间和空间都更贵。2. 拿到新题怎么想状态一个可复用的五步框架状态定义是整个动态规划的魂。我见过太多人卡在第一步看到题目不知道dp[i]该表示什么。这里给大家一套我用了很多年的思考流程几乎适用所有DP题。2.1 五步框架的具体内容第一步确定维度。思考问题是单序列、双序列、区间、还是棋盘/图上的路径维度的数量一般和题目中“自变量”的数量一致。第二个串、区间左右端点、物品的数量和容量都可能是维度。第二步定义状态含义。一句话说清楚dp[维度]代表什么常见的有“前i个元素的最优值”“以第i个结尾的最长子序列长度”“区间[i, j]的最小代价”。这一步必须足够具体最好能写成注释。第三步写出转移方程。想清楚当前状态从哪些更小的状态转移过来。比如dp[i] max(dp[i-1], dp[i-2] x)或者dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)。转移方程里的每一项都要有实际意义不能瞎拼凑。第四步确定边界条件。下标从哪里开始dp[0]和dp[1]是多少空集怎么办边界写错是整个DP最容易全军覆没的地方。第五步设计遍历顺序。自顶向下递归不需要管顺序自底向上循环必须保证计算dp[i]的时候它依赖的所有dp[j]都已经算完。背包问题里遍历顺序甚至决定结果是01背包还是完全背包这一点后面细讲。2.2 用爬楼梯实战一遍以经典的爬楼梯为例每次可以爬1级或2级问爬到第n级有几种不同方法。按五步走只有n一个变量所以是一维DP。状态定义dp[i]表示爬到第i级台阶的方法数。转移最后一步要么从i-1跨一级要么从i-2跨两级所以dp[i] dp[i-1] dp[i-2]。边界dp[0]1在地面上算一种状态dp[1]1。实际代码如下def climb_stairs(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]你发现没有这个dp数组其实和上面的斐波那契完全一样。不同的问题只要模型相同代码骨架就是同一套。这也是刷题多了以后能“看题型”的原因。2.3 再上一个稍难的打家劫舍“打家劫舍”这道题是面试高频也特别适合用来理解状态转移的选择逻辑。题目是一排房子每间有金额nums[i]相邻两间不能同时偷问最多能偷多少。状态定义dp[i]表示偷到第i间房为止能获得的最大金额。转移时有两种决策不偷第i间则金额等于dp[i-1]偷第i间则金额等于dp[i-2] nums[i]。两者取最大def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i-1], dp[i-2] nums[i]) return dp[n-1]注意dp[1]不能直接写成nums[1]因为前两间里只能偷一间时当然要偷钱多的那间。很多新手在这里写错边界结果样例都过不去。这道题的价值在于它让你明白转移方程其实就是在“选”和“不选”之间做比较所有DP都在做这个比较只不过选择标准不同。3. 两类最高频模型线性DP与背包问题刷题刷到中期你会发现动态规划虽然题目千变万化但有几种模型出现频率极高。先把线性DP和背包吃透后面学什么都有底气。3.1 线性DP之最长上升子序列LISLIS说的是在一个序列里找一个最长的严格递增子序列子序列可以不连续。比如[10, 9, 2, 5, 3, 7, 101, 18]的LIS长度是4对应[2, 3, 7, 101]。定义dp[i]为“以nums[i]结尾的最长上升子序列长度”。转移dp[i] max(1, max(dp[j] 1))其中j i且nums[j] nums[i]。def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个解法是O(n^2)。如果你要应对大规模数据就得换一个思路维护一个tails数组tails[k]表示长度为k1的上升子序列的最小结尾值。遍历数组时用二分查找找到第一个大于等于当前元素的位置并替换它。这么一优化复杂度降到O(n log n)同时代码也更简短import bisect def length_of_lis_nlogn(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)解法的朋友可能不理解它为什么正确。我的理解方式是tails并不是真正的子序列它只维护“长度相同的上升子序列里结尾能有多小”结尾越小后面接新元素就越容易。这其实带了一点贪心思想但整体还是靠DP的“状态转移”在驱动。3.2 01背包二维转一维的关键细节背包问题堪称DP界的“练功房”。01背包的题意很简单有n件物品每件重量w[i]、价值v[i]背包容量为C问能装的最大价值。每件物品最多拿一次。二维DP的状态定义是dp[i][j]前i件物品中选总重量不超过j的最大价值。转移不拿第i件dp[i][j] dp[i-1][j]拿第i件dp[i][j] dp[i-1][j-w[i]] v[i]前提是j w[i]所以dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。写成二维循环很好理解但很多题目要求优化空间。观察转移方程会发现第i行只依赖于第i-1行于是可以用一维数组反复更新vectorint dp(C 1, 0); for (int i 0; i n; i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }注意内层循环必须倒着遍历容量。为什么要倒因为如果正着遍历dp[j-w[i]]可能已经在当前物品循环里被更新过也就是说第i件物品被重复使用了这就不再是01背包而变成了完全背包。倒着遍历可以保证更新dp[j]时用到的dp[j-w[i]]还是上一轮的旧值。这个细节几乎每次面试都会有人问必须从原理上理解不能死记。3.3 完全背包为什么遍历顺序要反过来完全背包允许每件物品拿无限次。把上面代码的内层循环改成正着遍历就对了vectorint dp(C 1, 0); for (int i 0; i n; i) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }正着遍历时dp[j-w[i]]在同一个物品的循环里先被更新过于是“物品i还能再拿一次”这个信息被保留了正好符合完全背包的语义。背包类型内层循环方向含义01背包从大到小倒序每件物品最多选一次完全背包从小到大正序每件物品可选无限次多重背包二进制拆分后按01处理每件物品有固定数量上限顺便说一句如果题目要求恰好装满背包而不是不超过容量初始化就要把dp[0]设为0、其余设为负无穷代表“不合法状态”。很多新手在这个细节上栽跟头后面第5部分我会专门讲。4. 区间DP与实战模型从石子合并到车辆路径线性DP和背包做完之后就应该开始碰区间DP了。这类问题的特征是状态由两个下标表示一个区间转移时要枚举区间的分割点。4.1 石子合并区间DP的入门题题目背景一排石子每堆有数量a[i]每次只能合并相邻两堆代价是两堆数量之和问把所有石子合并成一堆的最小总代价。状态定义dp[i][j]表示合并区间[i, j]内的所有石子需要的最小代价。转移方程dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j))其中k从i枚举到j-1。sum(i, j)是区间内所有石子的总数可以用前缀和O(1)求。代码模板如下vectorvectorint dp(n, vectorint(n, INF)); for (int i 0; i n; i) dp[i][i] 0; for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] prefix[j1] - prefix[i]); } } }这里有个很重要的经验区间DP一定要先枚举区间长度再枚举起点不能直接先枚举i和j。原因很简单长度短的区间要先算出来后面的长区间才能依赖它。如果先按i从小到大、再按j从小到大dp[i][j]依赖的dp[k1][j]可能还没算出来。这个顺序问题在二维DP里比一维更隐蔽务必小心。4.2 树形DP和状态机DP知道有这回事刷完线性、背包、区间之后你可以接触树形DP和状态机DP。树形DP是把DP搬到了树上常见的套路是dfs递归处理子树然后在父节点汇总子节点的状态。比如“没有上司的舞会”这道经典题每个职员参加与否影响其下属状态就是dp[u][0/1]表示以u为根的子树、u不参加/参加时的最大欢乐值。状态机DP则适合那种“一个角色有多种模式、模式可以切换”的题比如股票买卖系列。买卖股票的最佳时机有冷冻期、有手续费这些约束都可以用“持有/不持有”两个状态来建模每天在这两个状态之间转移。说实话这类题把状态机和DP结合起来初看很难但你只要把状态图画出来转移方程其实就是图上的一条条边。这和强化学习里贝尔曼方程的思想如出一辙——价值函数更新就是状态价值的互相传递所以说DP是很多高级算法的基础一点不夸张。4.3 现实世界里的DP车辆动态规划问题很多人觉得DP只在OJ和面试题里有用其实它早就进入了工程领域。“车辆动态规划问题”这个词被搜索就不是没道理的物流公司的车辆调度、快递配送路线规划、电梯调度都可以建模成多阶段决策问题。比如车辆在一张有向无环图上从起点开到终点每个路口的等待时间和耗油量不同目标是总成本最小这本质上就是最短路DP——把状态设成“到达某个节点时的最小成本”按拓扑序更新即可。这类应用和算法题的区别是大数据量、带约束、需要和强化学习等结合。但底层的状态定义和转移思想仍然是最先被用到的东西。所以不要觉得刷DP题没用它是在训练你做工程决策时的建模直觉。5. 调试与避坑实录DP代码写错了怎么查用我自己的学生时代当反面教材吧。我刚开始刷DP时一份代码经常得改三四轮才能过样例很多时候不是思路错而是实现细节崩了。这些问题放到现在就特别好排查因为规律已经被无数人验证过了。5.1 常见错误速查表错误类型典型症状排查思路边界条件错误样例前几个能过后面突然崩检查dp[0]、dp[1]、空集情况必要时单独打印下标越界运行时报错或访问到负数下标检查遍历起点特别是需要j-w[i]0这种条件遍历顺序错误结果比答案大/小01背包变完全背包检查容量循环是正序还是倒序状态定义太粗转移方程推不出来回到五步框架重新想清楚dp的维度状态定义太细空间爆炸或者代码冗长尝试合并等价状态或者用滚动数组压缩数组初始化错误结果全为0或全为INF检查是否应该初始化为负无穷没有取模数值溢出结果错误数据范围超过10^9就考虑long long必要时取模DP数组没清空多组测试数据互相污染每组数据前重新initialize5.2 三个对我帮助极大的调试习惯第一个习惯是打印DP表。遇到情况不对不要急着改代码先把dp数组输出到控制台对着纸面上的小样例手动演算一遍找到第一个和预期不符的格子那个格子对应的状态定义或转移往往就是问题所在。这个坏毛病我改掉以后调试时间至少缩短一半。第二个习惯是写暴力程序对拍。在OJ上尤其是洛谷这种平台很多基础题都能用暴力枚举算法做小范围验证。我会写一个递归爆搜版本然后随机生成小规模数据把暴力结果和DP结果放在一起对比。当年我准备蓝桥杯的时候组里有个大佬用的就是这个套路代码通过率直接翻倍。第三个习惯是先把状态和转移写成注释。正式代码还没动笔先写下类似“dp[i][j]表示前i个物品装入容量j的背包的最大价值”这样的注释。如果注释本身都说不清楚代码大概率也写不对。这个方法听起来有点玄学但真的能逼你把问题想清楚比直接上手写代码稳得多。6. 面试和竞赛里的DP刷题策略与能力进阶到了最后一个部分聊一点实操层面的规划。我见过太多人一上来就啃难题结果被DP题目直接劝退。正确的打开方式是分层递进。6.1 面试高频DP题怎么准备算法工程师面试基本必考DP常问的题型就那么几件爬楼梯、打家劫舍、最长递增子序列、最长公共子序列、编辑距离、01背包。其中编辑距离这道题特别经典因为它同时考了二维DP、边界处理和状态转移的思维我建议每个准备面试的人都要手动推一遍它的状态定义dp[i][j]表示word1前i个字符转换成word2前j个字符的最少操作数。转移分为三种情况插入、删除、替换对应dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]三条路径。面试和笔试有个区别面试官更看重你“解释思考过程”的能力。就算一时间没有推出正确转移你也要把状态定义和几个样例的推演过程说出来这比闷头写代码有用得多。6.2 竞赛刷题路线从洛谷到蓝桥杯如果你目标是ACM/蓝桥杯这类竞赛我强烈建议把洛谷的动态规划题单当成主要训练场。那个题单从线性DP、背包到区间、树形、状压DP都有系统整理每一道都能在题解区看到大佬们的多种解法比我自己当年瞎刷强了不知道多少倍。建议的路线是先保证一类题刷熟再进下一类。比如先刷15-20道背包题做彻底了再碰区间DP。不要贪多更不要跳过基础直接做困难题。蓝桥杯和LeetCode必刷基础算法题都要覆盖但竞赛题更吃“题量”因为出题人喜欢把常见模型套上各种包装你要做到一眼看穿本质。6.3 说几句题外话我之前带过几个转行做算法的朋友他们的共同经验是DP真的就是“无他唯手熟尔”。第一道题可能要写一晚上第20道题能半小时AC第50道题看到题目就知道出题人在考哪个模型。我自己的体会是DP拉开差距的不是智商而是你在每个模型上投入的刻意练习量。每做完一道题多问自己一句“这道题的状态还能不能再优化”积累出来的手感会非常可怕。如果你现在正在被动态规划折磨别急把它当成练功写完代码再看一遍标准题解琢磨一下别人的状态定义和你的有什么不同这个过程比单纯AC有价值得多。