动态规划这块内容网上教程一抓一大把但多数要么堆公式把人劝退要么只给代码不讲为什么。我早期学的时候也踩过不少坑总觉得懂了换个题目又不会了。后来刷了几百道题、啃了几本经典教材才摸到门道。这篇东西我就按自己理解把动态规划的基本要素、解题步骤、优化思路和几个高频例题一次性讲透尽量用大白话把“为什么这么做”讲明白而不是丢一堆定义让你背。动态规划听上去高大上其实本质上就是一种“聪明的穷举”——把一个大问题拆成有重叠关系的子问题把子问题的答案记下来避免重复计算再用子问题的答案拼出大问题的答案。它不是什么奇技淫巧而是一套极其朴素的思维框架状态定义、状态转移方程、边界条件。只要这三样东西捋清楚了一道动态规划题基本就解决了八成的思考量。这篇文章适合刚接触算法、被递归和搜索折磨过的同学也适合刷题卡在中等难度动态规划想要突破的人。工作里做路径规划、资源调度、预算分配这类问题的朋友同样能从中找到可落地的思路因为动态规划的实际应用比我早先想象的广泛得多。1. 先搞清楚动态规划在解决什么问题1.1 什么题该用动态规划判断一个问题能不能用动态规划我一般是看两个信号。第一个信号是问题可以拆成子问题。比如斐波那契数列f(5)依赖f(4)和f(3)f(4)又依赖f(3)和f(2)子问题之间相互嵌套天然具备递归结构。很多看似无从下手的问题一旦你发现“规模小一点的同类问题”存在就说明有拆解的潜力。第二个信号是子问题会重复出现。还是拿斐波那契说事如果用裸递归去算f(5)f(3)会被重复计算两遍f(2)会被计算三遍。当n稍微大一点重复量会指数级膨胀。这种“同一个子问题被反复求解”的现象就是重叠子问题。动态规划的核心手段就是把算过的结果存起来下次直接查表。这两个信号缺一不可吗其实不完全是。有些问题虽然能拆成子问题但子问题之间互不相关、没有重叠那就要考虑分治法而不是动态规划。比如归并排序左右两半排序后合并左右子问题完全独立不存在共享计算结果所以是分治。动态规划之所以叫“动态”就是因为在子问题之间存在相互依赖、层层递进的关系。1.2 用生活场景理解状态和转移光说术语容易飘我拿一个特别接地气的例子来讲。假设你在爬楼梯一次可以跨一阶或者两阶问爬到第n阶一共有多少种爬法。这个问题怎么理解“状态”状态就是“当前爬到了哪一阶”。你站在第i阶这个事实就是一个状态。而“从第i-1阶跨一步到第i阶或者从第i-2阶跨两步到第i阶”这个动作就是状态之间的转移。所以爬到第i阶的方法数等于爬到第i-1阶的方法数加上爬到第i-2阶的方法数。这就是状态转移方程。边界条件是爬到第1阶有1种方法爬到第2阶有2种方法。有了状态、转移、边界整个问题就闭环了。这类比能帮你想明白一件事动态规划不是在瞎猜答案而是在枚举所有可能路径的同时把所有重复计算全部省掉。爬楼梯的每种爬法本质上是一条路径动态规划做的事就是把“从起点到某一状态的最优/计数结果”记住然后往后传递。2. 动态规划三大基本要素详解2.1 重叠子问题重复计算是性能杀手重叠子问题是动态规划能不能成立的基石。如果没有重叠子问题你把结果存到表里其实没什么意义因为每个子问题只用一次存了也白存。怎么判断有没有重叠子问题有个土办法画出递归调用树看同一个参数有没有被多次传入。比如一个递归函数solve(i)里同时调用了solve(i-1)和solve(i-2)那么solve(i-2)既会被solve(i)直接调也会被solve(i-1)调这个节点就重叠了。递归层数越深重叠越严重动态规划的收益就越明显。我在实际写代码时遇到递归超时的第一反应就是去查重叠子问题。如果确认重叠就立刻改成记忆化搜索——先按递归思维写再用字典或数组把已经算过的结果缓存起来。这样既保留递归代码的直观性又获得动态规划的性能。等确认思路没问题再改成迭代递推性能还能再上一个台阶。2.2 最优子结构子问题最优才能拼全局最优动态规划的第二个基本要素是最优子结构。这句话读起来很学术翻译一下就是大问题的最优解能由子问题的最优解组合出来。比如最短路径问题从A到C的最短路径如果经过B那么从A到B这一段一定也是最短的。如果不是你换一条更短的A到B路径整个A到C路径就更短了矛盾。这就是最优子结构的证明思路——反证法。有的题目没有最优子结构那就不能直接用动态规划。比如求“全局最长递增子序列”的某条具体路径子问题的最优路径不一定能拼接出全局最优路径这种情况就得先看能否换一种状态定义让最优子结构重新成立。你在设计dp数组时要反复问自己一个问题dp[i]这个子问题的最优解能不能在后续计算中通过某种方式拼接到更大的状态里想不明白的话八成是状态定义错了。这是很多初学者栽跟头的地方。他们喜欢一步到位去定义dp[n]代表最终答案但真正的老手会先想当前状态能不能由更小的状态转移过来转移后的结果是否仍具有“最优性”。想清楚了再写代码就不容易白费功夫。2.3 状态转移方程把口语逻辑翻译成数学公式状态转移方程是动态规划的心脏。它描述了状态之间如何依赖、如何推进。很多人觉得动态规划难的根源就是卡在状态转移方程这一步——面对题目不知道从哪里下手。我的经验是分三步走。先把口语逻辑说清楚比如“到第i天的最大利润要么是前一天的最大利润要么是这一天卖出股票的利润。”再用符号表示出来利润 max(dp[i-1], prices[i] - min_price)。最后检查边界情况比如i等于1时dp[0]是多少数组越界没有。在写转移方程之前一定要先做一件事确定遍历方向。有的状态从左往右推有的需要从右往左推有的甚至要两三层循环嵌套。遍历顺序错了状态依赖的先后关系就乱了。怎么判断方向就看当前状态依赖的是哪些之前的状态保证先算被依赖的状态就行。还有一类问题是区间动态规划状态依赖的是小区间的结果遍历时就要按区间长度从小到大来。这种题一上来也别慌记住这个规律——先枚举区间长度再枚举起点最后枚举分割点整个过程就顺了。3. 基础解题五步法从读题到AC的完整套路3.1 五步法总览我把动态规划的解题过程固定为五个步骤刷题时候照着做基本不会跑偏。明确状态定义想清楚dp[i]代表什么下标含义是什么。推导状态转移方程想清楚dp[i]怎么由之前的状态算出来。初始化边界条件把dp的初始值设置好保证递推能启动。确定遍历顺序决定外层循环和内层循环的先后保证依赖的状态已经算完。举例推导验证手算小规模数据看dp数组的变化是否符合预期。这个方法不是我自己拍脑袋定的很多经典教材里都有类似框架。好处是让你在面对陌生题目时有一个稳定的“破题顺序”而不是东想一下西想一下。3.2 每一步的操作技巧第一步明确状态定义是整个过程中最重要的也是最容易出错的。状态定义有问题后面全盘皆输。一个合格的状态定义至少满足两个条件能覆盖所有维度的信息能通过较小状态推出较大状态。如果你发现转移方程里需要知道的信息在dp数组里根本存不下就得考虑加维度比如dp[i][j]表示“前i个物品在容量j下的最大价值”。第二步推导状态转移方程时我常用的思路是“最后一步法”。问自己如果我想得到dp[i]那么最后一次操作是什么把最后一步枚举一遍然后把每种可能都跟前一步的状态联系起来。比如01背包里最后一个物品要么放入背包要么不放。不放就是在前i-1个物品里选放就是从前i-1个物品里选且背包容量减少w[i]两种情况取最大值即可。第三步初始化边界条件通常是dp[0]或者dp[1]。边界条件是递推的“点火器”没设好整个递推链条就断了。有些题还要考虑dp数组的默认值比如求最小值时dp初始化为一个很大的数求方案数时dp[0] 1。第四步遍历顺序这里面讲究很多。一维DP无论是正序还是倒序都会直接影响状态是否被“污染”。比如后面要讲的01背包空间优化版内层循环必须倒序遍历否则一个物品会被用多次。这其实不是玄学而是因为正序遍历时更新后的dp[j]会被后续的dp[j w[i]]再次使用等价于把同一个物品放入了多次。第五步举例验证。这一步很多人嫌麻烦跳过但我强烈建议做。拿一两个小例子手推一遍dp数组往往是捕捉逻辑漏洞的最快方式。我在面试时也经常用“你拿这个例子走一遍”来测试候选人是不是真的理解了自己的代码而不是背模板。3.3 常见错误与调试手法动态规划题常见的坑就那几个。第一个是下标越界尤其是涉及i-1、i-2时循环开头必须做好边界判断。第二个是初始值设置错误求最大值时初始化为0没问题但求最小值时初始化为0就是灾难。第三个是状态定义不清导致转移方程漏情况这种情况最隐蔽因为小样例可能恰好能过提交就挂。调试动态规划有一个利器——打印dp表。不要光看代码把每一步dp数组的变化都打出来跟手推结果对比你就能看到状态在哪一步脱离了预期。这个过程就像看监控录像回放能直接定位到是哪条转移路径出了问题。还有一个调试技巧是先用记忆化递归写一版用小数据验证正确性然后再改成迭代版本。递归版逻辑更贴近状态定义本身容易排查错误。确认正确后再优化成迭代版因为迭代版有些边界和遍历顺序问题一旦出错很难看清逻辑。4. 例题详解从入门到经典背包问题4.1 爬楼梯最简单的动态规划入门爬楼梯是动态规划的“Hello World”。题目说一次可以爬1阶或2阶问爬到第n阶有多少种方法。状态定义dp[i]表示爬到第i阶的方法数。 状态转移方程dp[i] dp[i-1] dp[i-2]。 初始化dp[1] 1, dp[2] 2。 遍历顺序从3到n正序。用Python写就是def climb_stairs(n: int) - int: if n 1: return 1 if n 2: return 2 dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这里顺带说一下空间优化。因为dp[i]只依赖前两个状态没必要存整个数组用两个变量滚动即可def climb_stairs_optimized(n: int) - int: if n 1: return 1 prev2, prev1 1, 2 for i in range(3, n 1): prev2, prev1 prev1, prev1 prev2 return prev1当n很大时爬楼梯还能用矩阵快速幂做到O(log n)但那就是另一套数学工具了初学者先掌握常规做法就行。这类“第n项只依赖前几项”的题目在动态规划里属于最简单的一类主要用来帮助你建立状态和转移的感觉。4.2 最少硬币问题最经典的最值型动态规划题目再熟悉不过给定不同面额的硬币coins和一个总金额amount求凑成总金额所需的最少硬币个数。如果无法凑成返回-1。状态定义dp[i]表示凑成金额i所需的最少硬币数。 状态转移方程dp[i] min(dp[i - coin] 1)其中coin是所有小于等于i的硬币面额。 初始化dp[0] 0其余位置初始化为一个很大的数比如amount 1因为这个数在正常情况下不可能达到。 遍历顺序外层循环金额i从1到amount内层循环硬币面额coin。完整代码def coin_change(coins: list[int], amount: int) - int: dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1我在这里强调一个细节为什么初始化用amount 1而不是float(inf)其实都行用整数能避免类型混用带来的坑。在任何语言里我都习惯用一个“绝对不会出现的大数”来做不可达标记比较起来也更安全。这个题的关键在于“最后一步法”凑成金额i最后一枚硬币是什么面额如果是coin那么前一步就是金额i - coin。把coins内所有面额都枚举一遍取最小值。你要注意这里硬币数量是无限的所以内层循环可以重复使用同一面额不会违反规则。如果你把外层循环换成“先遍历硬币再遍历金额”得到的是另一个结果——每种硬币只能用一次。这两种写法分别对应“完全背包”和“0/1背包”细节上差之毫厘语义上就完全不一样了。做动态规划题一定要搞清楚循环顺序对状态覆盖的影响。4.3 01背包问题动态规划分水岭01背包可以说是动态规划里的“分水岭”题。题目描述有n个物品每个物品有重量weight[i]和价值value[i]背包容量为capacity每个物品最多选一次问能装下的最大价值是多少。状态定义dp[i][j]表示前i个物品在背包容量为j时能获得的最大价值。 状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。 初始化dp[0][j] 0表示前0个物品价值为0。 遍历顺序外层物品i内层容量j从0到capacity正序。二维版本代码def knapsack_2d(weights: list[int], values: list[int], capacity: int) - int: 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): if j w: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) else: dp[i][j] dp[i - 1][j] return dp[n][capacity]这里有个地方要注意dp数组第一维是“前i个物品”所以物品下标从1开始weights和values要取i-1。这是新手经常写错的地方。接下来是空间优化版本。dp[i][j]只依赖dp[i-1][...]所以可以用一维数组滚动更新。但内层循环必须倒序遍历def knapsack_1d(weights: list[int], values: list[int], capacity: int) - int: 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]为什么内层要倒序因为正序遍历时dp[j - w]可能已经被当前物品更新过这时候就会出现“把当前物品装进去后又装了一次当前物品”的情况。这不是01背包想要的倒是完全背包里恰好需要这种效果。所以记住01背包一维优化容量倒序完全背包一维优化容量正序。这句话背下来能省很多调试时间。01背包的思维模型能延伸到大量实际问题里比如资源分配、任务调度、预算规划甚至我在后面会提到的线材切割优化本质上都能抽象成“有限资源下价值最大化”的模型。5. 算法优化从能跑到跑得快5.1 空间优化滚动数组与状态压缩空间优化是动态规划最常见、收益最直接的优化手段。核心思想很简单如果dp[i]只依赖dp[i-1]或者dp[i-2]那我就不需要保存整个二维表只用两个一维数组甚至两个变量就够了。爬楼梯我用两个变量完成了滚动。01背包我用一维数组完成了状态压缩。这类优化的本质都是“去掉不会再用到的历史状态”。在做空间优化前先画一下状态依赖图看看每个状态到底依赖谁。只要依赖范围是“上一层”、“前一行”这种固定距离就能滚动。还有一类更隐蔽的空间压缩比如在网格路径问题里如果用滚动数组可以把二维dp压到一维但要注意遍历顺序和覆盖方向。这种情况下我会专门用笔把旧值和新值的分布画出来确认压缩后不会覆盖掉还没用到的数据。5.2 常数优化与剪枝技巧除了空间时间上也有些实用的小优化。最常见的是提前终止和剪枝。比如在最少硬币问题里如果当前金额已经不可能成为最优解可以跳过。在背包问题里如果所有物品总重量不超过背包容量那直接返回总价值就行。另一个实用技巧是“单调队列优化”。有些状态转移方程里dp[i] max(dp[i-k] cost)的形式如果k的范围固定可以用单调队列把内层循环从O(n)优化到O(1)。典型如滑动窗口最大值类的问题。这类优化在竞赛里常见但对业务开发来说有点进阶了掌握概念和适用场景就够不用每一题都套。5.3 进阶优化四边形不等式与斜率优化再往上走就是四边形不等式优化和斜率凸包优化。这两种优化的适用场景比较明确当dp[i][j] min(dp[i][k] dp[k][j] cost)这类区间划分问题时如果cost满足四边形不等式那么最优决策点具有单调性可以大幅缩小枚举范围这就是四边形不等式优化。斜率优化则用于形如dp[i] min(dp[j] a[i]*b[j] c[j])的转移方程。这种形式下可以看作一条直线在某个位置的截距最值问题用凸包维护候选点即可。我不建议初学者一上来就攻读这些先把常规动态规划刷熟遇到需要优化的题目时再针对性地学习思维负担会小很多。5.4 动态规划在真实业务中的应用讲点更现实的东西。很多人学动态规划只为了面试刷题容易忽略它在真实世界的价值。实际上动态规划在路径规划、物流调度和工业优化里非常常见。比如车辆路径规划问题一辆车在一个城市网络中从起点到终点求最短时间或最低油耗。城市规模不大时状态可以定义为“当前所在节点已访问节点集合”再用状态压缩动态规划求解这就是旅行商问题的经典解法。如果节点数量稍微大一点则可以引入近似算法和启发式算法但这些算法的很多初始化方案仍然依赖动态规划结果。再如工业界常见的线材切割优化问题需求是把长度不一的原材料切割成不同规格的小段目标是废料最少。这本质上是一个一维下料问题可以用动态规划来建模dp[i]表示切割出总长度为i的所有需求时的最小废料量。如果你了解过“线材优化python算法”这类关键词会发现网上有很多完整实现核心思路就是物品无限使用的完全背包变种。我个人的体会是学动态规划最值钱的不是记住几道题而是养成“找状态、找转移、找边界”的思维方式。就算以后不做算法岗在写代码时遇到一个多阶段决策问题你也会自然地问自己这个问题能拆吗子问题重叠吗能记录中间结果吗6. 总结一套自己的复盘方法写到这里我把动态规划的完整思考路径串一下。拿到一道题先判断它是不是多阶段决策问题再看子问题是否重叠。确认后定义状态、写转移方程、设边界、定遍历顺序最后用小样例验证。这是所有人的必经之路没有捷径。但在实际操作中我建议你建立一个“动态规划错题本”。记录每道题的题目类型、状态定义、为什么这样定义、转移方程踩了什么坑、边界条件卡在哪。这个习惯我保持了很久效果非常好。因为动态规划的题型是有规律可循的记下几类经典状态定义方式后新题不过是旧题型的变体。另外我踩过几次坑之后的一个经验是不要在拿到题的瞬间就急着码代码。先花几分钟在白纸上写状态定义和转移方程哪怕写得潦草也没关系这个过程会强迫你的思路变得清晰。写完再动手代码基本一遍过。我也见过太多同学读题一分钟写代码半小时最后debug两小时问题几乎都出在状态定义不清和遍历顺序错乱上。最后再分享一个小技巧遇到动态规划卡壳时尝试把题目改成更小规模的实例手工推一遍。这个过程看似费时实际是帮你建立“状态变化直觉”的最好方式。推着推着你往往就会“啊原来这里应该这样定义状态”。这种顿悟式体验比看十篇教程都管用。