动态规划这四个字很多人第一次听到是在算法课上第二次听到就是在面试挂掉之后的复盘里。我这些年带过不少刚入行的朋友也跟做路径规划、资源调度的工程团队打过交道发现一个挺有意思的现象动态规划难不是难在代码写不出来而是难在“想不出来”。代码往往就十几行但那个状态怎么定义、转移怎么写能把人卡一整天。这篇内容我打算把动态规划从头到尾捋一遍既讲清楚它为什么这么设计也把几道经典题从头推一遍把参数、边界、遍历顺序这些容易翻车的地方都摊开说。不管你是刚接触算法的新手还是刷了几十道题仍然“看题解秒懂、自己写就懵”的朋友下面这些内容应该都能对得上你的痛点。我会尽量少讲空话多讲我当时是怎么想通的、哪些坑我亲手踩过。1. 先把动态规划这件事说透它到底在解决什么问题动态规划Dynamic Programming简称 DP本质上不是一种“算法”而是一种思考方式把一个大问题拆成一串互相重叠的小问题把每个小问题的答案存下来后面用到的时候直接查表不再重算。这个定义听起来平平无奇但它解决的是一个非常实际的痛点——重复计算。你可以先记住一句话动态规划 递归的骨架 记忆化的灵魂 递推的实现。三者缺一个理解就会断层。1.1 从递归爆炸到记忆化DP 的诞生逻辑先看一个所有人都写过的递归求斐波那契数列第 n 项。最朴素的写法是f(n) f(n-1) f(n-2)代码三行逻辑清晰。但你拿 n40 跑一下就会发现它慢得离谱原因不在于递归本身慢而在于它把同一件事干了无数遍。算 f(40) 要算 f(39) 和 f(38)算 f(39) 又要再算一遍 f(38)这棵递归树的分支数量是指数级膨胀的。我当年第一次看到这个复杂度分析时挺震惊的明明只是加法怎么会跑到 2 的 n 次方去。解决思路有两条路。第一条是记忆化搜索递归照写但加一个数组或者哈希表算过的结果存进去下次进来先查表有就直接返回。这一步改动极小复杂度立刻从指数级掉到线性级因为每个状态最多算一次。第二条是递推既然 f(n) 只依赖 f(n-1) 和 f(n-2)那干脆从 f(1)、f(2) 开始往上推一路推到 f(n)。这就是所谓的“自底向上”。这两条路其实是同一件事的两种表达。记忆化搜索是“我需要什么就算什么”递推是“我按顺序把所有的都算好”。理解了这层等价关系后面看任何一道 DP 题都不会觉得突兀你完全可以在脑子里先想递归怎么写再想怎么把它变成递推。我自己做题的习惯就是先写暴力递归再琢磨哪些状态重复了最后改成递推或者加记忆化。这个顺序比一上来就硬想递推公式要稳得多。1.2 什么样的问题才配用动态规划不是所有问题都能套 DP。判断一个问题能不能用我一般看三个条件缺一不可。第一个是最优子结构。也就是大问题的最优解必须能由小问题的最优解拼出来。比如最短路径问题从 A 到 C 的最短路径如果经过 B那 A 到 B 和 B 到 C 也一定分别是这两段的最短路径否则你把其中一段换得更短整体就跟着变短了矛盾。反过来说如果一个问题拆开之后子问题的最优解拼不回原问题的最优解那就不能用 DP。第二个是重叠子问题。子问题必须被反复用到否则你存表就是白存。分治算法拆出来的子问题通常是互不相交的比如归并排序左半边和右半边各排各的没有重叠那就老老实实用分治别硬套 DP。第三个是无后效性。这词听着玄说白了就是一旦某个状态确定了后面怎么走只跟这个状态本身有关跟“你是怎么走到这个状态的”无关。举个反例如果题目要求“走过的路径不能重复”那当前状态光记录“我在哪”不够还得记录“我去过哪些地方”状态空间瞬间爆炸这时候 DP 就不太合适了。提示判断无后效性有个笨但有效的办法——问自己“如果两个不同的历史过程走到了同一个状态后面的决策会不会不一样”。会就说明状态定义漏了信息不会就说明状态定义够用。1.3 和贪心、分治、回溯的边界在哪这几种方法经常被混着讲实际用起来边界挺清楚的。贪心每一步都选当前看起来最好的不回头它的前提是“局部最优能推出全局最优”这个前提很多时候不成立所以贪心要么特别简单要么特别难证。分治把问题拆成互不重叠的子问题各自求解再合并典型代表是排序和快速幂。回溯是穷举所有可能性剪枝做得好能过做不好就超时。动态规划则是穷举的“聪明版本”——它把所有可能的状态都算一遍但每个状态只算一次。举个具体例子找零钱问题给你若干面额的硬币问凑出金额 m 最少要几枚。如果面额是 1、5、10 这种规整的贪心从大到小拿就行。但如果面额是 1、3、4要凑 6贪心会先拿 4 再拿 1 再拿 1三枚而最优解是 33两枚。这就是贪心翻车的经典场景而 DP 能稳定给出正确答案。我一般建议拿不准的时候先想 DP等你想清楚了贪心的正确性证明再换成贪心因为贪心错了很难查DP 慢一点但至少结果是对的。2. 动态规划的四步拆解法状态、转移、初始化、遍历刷题刷到一定量之后我发现所有的 DP 题都能归到同一套流程里定义状态、写转移方程、处理初始化和边界、确定遍历顺序。这四步里第一步和第二步决定了你能不能做出来第三步和第四步决定了你的代码会不会在某个测试用例上莫名其妙地挂掉。很多“思路对了但一直 WA”的情况问题都出在后两步。2.1 状态定义整道题的地基状态定义是 DP 里最吃经验的一步也是最没有标准答案的一步。所谓状态就是“用一个或几个变量把当前局面的关键信息描述清楚”。关键在于“关键”两个字——信息太少后面推不下去信息太多状态空间爆炸。我常用的一个思考套路是先看题目问什么再看决定答案的因素有哪些。比如问“前 i 个物品里选容量为 j 时的最大价值”那两个变量i和j天然就是状态的两个维度。再比如问“以第 i 个元素结尾的最长递增子序列长度”注意这里是“以第 i 个结尾”不是“前 i 个里最长的”这个差别很要命前者能保证无后效性后者不能。这个坑我在最长递增子序列上栽过不止一次后面第 3 节会展开讲。状态定义还有一个实用技巧把“答案”本身作为状态的一部分。比如问“能不能凑出金额 j”那状态就是dp[j] true/false问“凑出金额 j 有几种方式”状态就是dp[j] 方案数问“凑出金额 j 最少几枚硬币”状态就是dp[j] 最小数量。同一道题的骨架换个问法状态的含义跟着变转移方程也跟着变但整体的推导流程是完全一样的。2.2 状态转移方程把大问题拆成小问题转移方程说白了就是一句“当前状态从哪些旧状态推过来”。写的时候我一般会问自己两个问题最后一步做了什么以及做完这一步之前局面是什么样的。这两个问题回答清楚了方程基本就出来了。拿背包举例。考虑第 i 个物品最后一步只有两种可能要么把它放进去了要么没放。如果没放那当前价值就等于“前 i-1 个物品、容量 j”的价值如果放了那当前价值等于“前 i-1 个物品、容量 j-w[i]”的价值再加上 v[i]。两种可能取最大方程就写完了。这个“最后一步分类讨论”的思路适用于绝大多数 DP 题尤其是计数类和最值类。写方程的时候有几个细节值得注意。取最大值时别忘了考虑“不选”这个选项很多人写方程只写了“选”的分支漏了“不选”结果答案偏小。计数类问题要注意去重比如爬楼梯如果一次可以走 1 步或 2 步那f(n) f(n-1) f(n-2)是对的因为最后一步走 1 步和走 2 步是互斥的两种情况不会重复但如果题目改成“可以走任意步数”那方程就完全不一样了。带限制条件的问题要把限制写进状态里比如“最多只能选 k 个”那就得加一维dp[i][j][k]。2.3 初始化与边界最容易翻车的地方我见过太多人思路完全正确代码写出来也对就是过不了最后发现是初始化错了。初始化这件事看着琐碎但它是整个递推的起点起点错了后面全是错的。最典型的坑是“求最小值”的题目里把 DP 数组初始化成 0。0 在求最大值时是安全的因为价值非负不选就是 0但在求最小值时是灾难性的——所有没被更新的位置都停留在 0最后答案就是 0看起来还挺合理实际上完全错了。正确的做法是初始化成一个足够大的数比如float(inf)或者一个明显超过答案范围的值同时在转移时判断“这个状态是否可达”避免从不可达状态转移过来。另一个坑是下标从 0 开始还是从 1 开始。我的建议是只要涉及“前 i 个”这种表述一律把 DP 数组开大一位用下标 1 表示“前 1 个”下标 0 表示“一个都没选”的空状态。这样转移方程的边界会干净很多dp[0][...]就是天然的初始状态不用到处写if i 0的特判。多开一位内存的代价可以忽略换来的是代码可读性和正确性的大幅提升。注意初始化不只是“把数组填个初值”还包括“哪些状态在起点是合法的”。比如背包问题里dp[0][j] 0表示一个物品都不选时价值为 0这是合法的但如果题目要求“必须恰好装满”那dp[0][0] 0而dp[0][j0]应该是不可达这两者的区别决定了最后答案取哪个位置。2.4 遍历顺序决定你能不能拿到正确的子问题解遍历顺序的核心原则只有一条当你计算dp[i][j]时它依赖的所有状态必须已经算好了。听起来是废话但实际写的时候特别容易搞反。二维 DP 一般是外层循环 i内层循环 j因为dp[i][j]通常依赖dp[i-1][...]外层按 i 递增就能保证上一行已经算完。但一维 DP 就微妙了尤其是背包问题压缩成一维之后内层循环的方向必须反过来。原因很简单一维数组里dp[j]在更新前存的是“上一行”的值更新后存的是“当前行”的值。如果你正序遍历dp[j-w[i]]可能已经被当前物品更新过了相当于同一个物品被用了多次那就变成完全背包了。这个点在 4.2 节会详细展开。还有一种情况是依赖方向不是“上一行”而是“左边和上边”比如编辑距离、最长公共子序列这类题的遍历顺序是标准的从左到右、从上到下不会出问题。真正需要小心的是那些依赖“同一行的其他位置”的题比如区间 DPdp[i][j]依赖dp[i][k]和dp[k1][j]这时候必须按区间长度从小到大遍历先算短区间再算长区间。3. 从零手推三道经典题把四步法跑一遍光讲方法论容易飘下面我挑三道最有代表性的题把四步法从头到尾跑一遍。这三道题分别对应“线性递推”“二维背包”“序列型 DP”覆盖了日常刷题里八成以上的场景。代码我用 Python 写因为可读性最好逻辑一眼能看清换成 Java 或 C 只是语法差异。3.1 爬楼梯最小闭环理解递推题目很简单有 n 级台阶每次可以走 1 级或 2 级问走到第 n 级有多少种走法。这道题是理解 DP 的最佳入口因为它足够小小到你可以把每一步都在纸上画出来。第一步定义状态dp[i]表示走到第 i 级台阶的走法数。第二步写转移走到第 i 级最后一步只有两种可能——从第 i-1 级走 1 级上来或者从第 i-2 级走 2 级上来。这两种情况互斥且完备所以dp[i] dp[i-1] dp[i-2]。第三步初始化dp[0] 1表示站在地面上一种走法什么都不做dp[1] 1走到第 1 级只有一种走法。第四步遍历i 从 2 到 n 正序递推。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[i]只依赖前两项空间可以从 O(n) 降到 O(1)。第二这道题的dp[0] 1是有争议的有些人觉得“站在地面上”不算一种走法应该设成 0。如果你是设成 0那 n2 的时候就会算错。我个人的经验是凡是“从起点走到终点”的计数题起点的方案数一般设成 1因为“什么都不做”也是一种合法方案这样递推才自洽。3.2 0-1 背包二维到一维的降维打击背包问题是 DP 里绕不开的一座山也是最能体现“状态定义影响复杂度”的题。题目是有 n 个物品第 i 个物品重量 w[i]、价值 v[i]背包容量为 C每个物品最多选一次求能装下的最大价值。状态定义dp[i][j]表示考虑前 i 个物品、背包容量为 j 时能获得的最大价值。转移方程对第 i 个物品要么不选要么选前提是 j w[i]。dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])注意第二项里是dp[i-1]而不是dp[i]这是 0-1 背包和完全背包的唯一区别。0-1 背包每个物品只能用一次所以选完第 i 个之后剩下的容量只能从前 i-1 个物品里选完全背包物品无限选完还能继续选第 i 个所以是dp[i][j - w[i]]。初始化dp[0][j] 0一个物品都不选价值为 0。遍历外层 i 从 1 到 n内层 j 从 0 到 C。def knapsack_2d(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w, v weights[i - 1], values[i - 1] for j in range(capacity 1): dp[i][j] dp[i - 1][j] if j w: dp[i][j] max(dp[i][j], dp[i - 1][j - w] v) return dp[n][capacity]这段代码里我特意把“不选”单独写出来而不是塞进 max 里原因是如果 j w第二项根本不存在直接访问会越界。很多人为了代码短写成max(dp[i-1][j], dp[i-1][j-w]v)然后加个 if 判断逻辑上没错但可读性差一些。这里有个细节值得单独说为什么返回值是dp[n][capacity]而不是max(dp[n])。因为背包不要求装满容量为 capacity 时的最优解一定不小于容量更小时的解容量更大可选空间只会更多不会更少所以dp[n][capacity]就是全局最优。但如果题目改成“恰好装满”那就得看dp[n][capacity]是否可达不可达就返回 -1这时候就不能想当然地取最后一个位置了。3.3 最长递增子序列状态定义的两种视角这道题是状态定义的反面教材集中营。题目给一个数组求最长严格递增子序列的长度。注意是子序列不是子数组元素可以不连续。错误的状态定义dp[i]表示前 i 个元素里的最长递增子序列长度。这个定义看着自然但推不下去因为dp[i]和dp[i-1]之间没有明确的递推关系——第 i 个元素加进来可能接在前面某个子序列后面也可能不接而你并不知道前面那个子序列的末尾元素是谁。正确的状态定义dp[i]表示以第 i 个元素结尾的最长递增子序列长度。这个“以……结尾”是关键它把末尾元素固定住了无后效性就有了。转移方程对每个 i往前找所有 j i 且 nums[j] nums[i] 的位置dp[i] max(dp[j]) 1。如果前面没有比它小的dp[i] 1自己单独成一个序列。def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)注意最后返回的是max(dp)而不是dp[n-1]因为最长递增子序列不一定以最后一个元素结尾。这个返回值的选择是这道题的高频错误点我第一次写的时候就在这上面挂了两个测试用例。这个 O(n²) 的写法理解起来直观但数据量大时会超时。优化到 O(n log n) 的思路是维护一个数组tailstails[k]表示长度为 k1 的递增子序列的末尾元素最小值。遍历每个元素用二分查找找到它应该替换的位置。这个优化的核心洞察是末尾元素越小后面能接上的可能性越大所以对同样长度的子序列我们只保留末尾最小的那个。这个思路第一次看会有点绕建议先把 O(n²) 写熟再去看优化版本。4. 空间优化与滚动数组把内存压到极致DP 的空间复杂度经常被人忽略因为大部分题 n 都在几百到几千二维数组开出来也没多少。但真到了工程场景比如序列比对、路径规划状态空间可能是几百万甚至上亿这时候空间优化就不是“锦上添花”而是“能不能跑起来”的问题了。4.1 什么时候能压什么时候不能压能不能压缩空间判断标准只有一个当前状态依赖哪些旧状态。如果dp[i][...]只依赖dp[i-1][...]那前面的所有行都可以扔掉只保留两行滚动。如果还依赖dp[i-2]那就保留三行。这就是所谓的滚动数组。爬楼梯是最好例子dp[i]只依赖dp[i-1]和dp[i-2]所以两个变量就够了def climb_stairs_optimized(n): if n 1: return 1 prev2, prev1 1, 1 for _ in range(2, n 1): prev2, prev1 prev1, prev1 prev2 return prev1但有些题是压不了的。比如区间 DP 里的dp[i][j]依赖dp[i][k]和dp[k1][j]依赖关系是二维的你没法用几行变量表示。再比如需要输出具体方案的题你必须保留完整的 DP 表才能回溯路径压了空间就回不去了。我一般的判断流程是先看依赖方向是不是单向的“上一层”是就能压不是就先别压等跑通了再说。4.2 背包问题一维数组的遍历方向为什么必须倒序这是背包问题里最容易被问、也最容易记混的点。一维背包的代码是这样的def knapsack_1d(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w, v weights[i], values[i] for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]内层循环从capacity倒着走到w为什么因为dp[j]更新时需要用到dp[j-w]。在二维版本里这个dp[j-w]来自上一行也就是“还没考虑第 i 个物品”的状态。压缩成一维之后同一个数组既存上一行的值又存当前行的值。如果你正序遍历dp[j-w]在j-w j的位置已经被当前物品更新过了那它就变成“已经考虑过第 i 个物品”的状态相当于第 i 个物品被重复使用这就是完全背包的语义了。倒序走的话dp[j-w]还没被当前物品碰过仍然保持着上一行的值语义就对了。这个结论我建议直接背下来但更重要的是理解它为什么成立。你可以拿一个只有一件物品、容量为 3、物品重量为 1、价值为 5 的例子手动正序跑一遍你会看到dp[3]变成 15 而不是 5那一刻你就永远记住了。提示完全背包的内层循环恰恰是正序的因为它的语义就是“物品可以重复用”。所以记住一句话就够了——0-1 背包倒序完全背包正序。两者的代码只差一个range的方向但含义天差地别。5. 常见问题与排查技巧实录DP 题的错误有个特点编译能过样例能过提交就挂而且挂了之后你盯着代码看半天也看不出问题。我这些年排查过的 DP bug 里八成以上都能归到下面几类。这部分我尽量写成“症状—原因—解法”的形式方便你直接对照。5.1 状态定义错了后面全白搭这是最致命也最难查的一类错误。症状通常是样例能过稍微复杂一点的用例就错而且错得毫无规律。原因是状态信息不够导致后面的转移拿了错误的数据。排查方法我一般用“反例法”构造两个不同的历史过程看它们是否会走到同一个状态但后续的最优决策不一样。如果会那就说明状态定义漏了信息。举个具体例子如果题目要求“路径上的数字不能重复”那状态只记录“当前位置”就不够因为两条不同的路径走到同一个位置能走的下一步可能完全不同。这时候要么把“已访问集合”加进状态状态空间爆炸要么换一种思路比如用状态压缩把集合压成一个整数。还有一种隐蔽的情况是状态含义和转移方程不匹配。比如你定义dp[i]是“前 i 个元素的最优解”但转移方程里却按“以第 i 个结尾”来写代码跑起来可能不报错但结果就是不对。这种错误只能靠“写完方程回头读一遍状态定义”来避免我现在的习惯是写完转移方程后用一句话把状态含义念出来看看和方程对不对得上。5.2 边界条件与数值溢出边界问题主要集中在这几个地方n0 或 n1 的特判、数组下标越界、不可达状态的表示。n0 的情况尤其容易被忽略很多人在本地测试的时候随手写个 n5根本想不到空输入会崩。数值溢出在 Python 里不明显因为整数是任意精度的但在 Java 和 C 里就是实打实的坑。比如求方案数答案可能超过int的范围得用long再比如求最小值时用Integer.MAX_VALUE做初始值转移时MAX_VALUE v直接溢出变成负数结果全错。正确的写法是加个判断或者用MAX_VALUE / 2这种安全的“足够大”的值。我把常见问题整理成了一张表方便对照症状可能原因排查与解决样例过提交挂状态定义缺信息构造反例检查两个历史过程是否混在同一状态答案恒为 0求最小值时初始化为 0未判断可达性初始化为无穷大转移前判断前置状态是否可达答案偏大0-1 背包内层正序遍历改为倒序遍历答案偏小转移方程漏了“不选”分支补上dp[i-1][j]这一项数组越界下标从 0 开始与“前 i 个”表述冲突DP 数组开大一位用下标 1 表示前 1 个结果总差 1返回值取错如 LIS 返回dp[n-1]改为返回max(dp)或dp[n][capacity]大数用例错整数溢出换long或对结果取模5.3 从暴力递归到 DP 的改造心法如果你实在想不出转移方程我的建议是别硬想先写暴力。写一个纯递归的版本不加任何优化然后把递归树画出来看看哪些节点重复了。重复的节点就是“重叠子问题”把它们的结果缓存起来就是记忆化搜索。记忆化搜索写出来之后再观察依赖关系通常就能自然改写成递推。这个流程的好处是每一步都很具体不需要“灵光一闪”。我带的几个朋友一开始都不信这个法子觉得暴力递归太笨后来试了几次发现真香——因为暴力版本至少保证了正确性改造成 DP 只是性能优化不会把逻辑搞崩。反过来说如果你连暴力版本都写不出来那说明你对题目的理解还不到位这时候硬套 DP 模板只会越套越乱。记忆化搜索还有个好处是它只计算真正需要的状态。有些题的状态空间很大但实际可达的状态很少这时候递推版本要遍历整个空间记忆化搜索却只走可达路径性能反而更好。当然代价是有递归栈开销状态数特别大的时候可能爆栈那就得老老实实改成递推。最后分享一个我自己做题时的小习惯每次写完 DP我会拿一个极小的用例n1、n2、容量为 0手动跑一遍把 DP 数组的每个格子写在纸上看看初始化和转移是不是符合预期。这个动作花不了两分钟但能挡掉至少一半的低级错误。踩过的坑多了就会发现DP 这玩意儿想清楚比写快重要得多而想清楚的最快方式往往就是把小例子摊开来手动走一遍。