动态规划这块内容，网上教程一抓一大把，但多数要么堆公式把人劝退，要么只给代码不讲为什么。我早期学的时候也踩过不少坑，总觉得懂了，换个题目又不会了。后来刷了几百道题、啃了几本经典教材，才摸到门道。这篇东西我就按自己理解，把动态规划的基本要素、解题步骤、优化思路和几个高频例题一次性讲透，尽量用大白话把“为什么这么做”讲明白，而不是丢一堆定义让你背。
动态规划听上去高大上，其实本质上就是一种“聪明的穷举”——把一个大问题拆成有重叠关系的子问题，把子问题的答案记下来避免重复计算，再用子问题的答案拼出大问题的答案。它不是什么奇技淫巧，而是一套极其朴素的思维框架：状态定义、状态转移方程、边界条件。只要这三样东西捋清楚了，一道动态规划题基本就解决了八成的思考量。
这篇文章适合刚接触算法、被递归和搜索折磨过的同学，也适合刷题卡在中等难度动态规划想要突破的人。工作里做路径规划、资源调度、预算分配这类问题的朋友，同样能从中找到可落地的思路，因为动态规划的实际应用比我早先想象的广泛得多。
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两小时，问题几乎都出在状态定义不清和遍历顺序错乱上。
最后再分享一个小技巧：遇到动态规划卡壳时，尝试把题目改成更小规模的实例，手工推一遍。这个过程看似费时，实际是帮你建立“状态变化直觉”的最好方式。推着推着，你往往就会“啊，原来这里应该这样定义状态”。这种顿悟式体验，比看十篇教程都管用。
