动态规划这四个字，大概是算法学习路上劝退率最高的名词之一。我一开始接触动态规划时，完全被"状态""转移方程""最优子结构"这些术语砸晕，一度怀疑是自己数学基础太差。后来刷了足够多题目、反复推演过几个经典模型才发现，动态规划本质上就是一套"用空间换时间、用小问题的答案拼出大问题答案"的思考方式，并没有传说中那么神秘。这篇文章就以我学习动态规划过程中最有体感的几个切入点为主线，从斐波那契数列讲到背包问题，把"为什么这么想""状态转移方程怎么来的""实际写代码时哪里容易翻车"全部摊开讲清楚，希望能帮正在动态规划门口徘徊的读者少走一段弯路。
1. 动态规划到底在解决什么类型的"麻烦"
1.1 一个看似简单却没法直接"算"的问题
先看一个经典场景：你正在爬一个 n 级台阶的楼梯，每次可以爬 1 级或 2 级，问有多少种不同的方法爬到楼顶。
这个问题初看好像不复杂，但真动手去列，n=10 的时候还好，n=30 的时候手动列举就已经不现实了。我最早拿到这道题的时候，第一反应是排列组合，想着"有 k 次走 2 级，剩下 n-2k 次走 1 级，然后算组合数"，但真算起来要考虑 k 取 0 到 n/2 的所有情况，还要处理组合数溢出，麻烦得很。
实际上这道题的正确打开方式是观察递推关系：如果想爬到第 n 级台阶，最后一步要么是从第 n-1 级跨 1 级上来，要么是从第 n-2 级跨 2 级上来。换句话说，爬到第 n 级的方法总数 = 爬到第 n-1 级的方法总数 + 爬到第 n-2 级的方法总数。
这个关系一旦写出来，题目就从一个"计数难题"变成了"已知前两项，按规律往下推"的简单问题。这就是动态规划最常见的切入点：把一个大问题拆成几个规模更小、结构相同的小问题，用递推的方式逐个击破。
1.2 三个关键词：重叠子问题、最优子结构、状态转移方程
动态规划相关的教程里，几乎每篇都会提到重叠子问题、最优子结构、状态转移方程这三个词。我当初看这些术语的时候，每个字都认识，但连在一起完全不知道在说什么。后来自己总结了一套不那么学术的理解方式：
重叠子问题：大问题分解出的若干小问题，会被重复计算很多次。比如爬楼梯问题中，计算 f(10) 需要 f(9) 和 f(8)，计算 f(9) 又需要 f(8) 和 f(7)，f(8) 被反复算了两次甚至更多。如果不做任何缓存，重复计算量会指数级膨胀。
最优子结构：大问题的最优解，可以由小问题的最优解组合得到。注意这里强调的是"最优解"，也就是说，只要小问题各自达到了最优，大问题就能基于这些小问题的最优结果构造出自己的最优解。如果一道题不满足这个特性，比如局部最优组合起来反而导致全局不是最优，那就不能用动态规划硬套。
状态转移方程：说白了就是"从已知小问题结果推导未知大问题结果的数学式子"。爬楼梯的状态转移方程就是 f(n) = f(n-1) + f(n-2)。写出这个方程，动态规划的核心工作就完成了一半以上。
1.3 为什么"会做这道题"不等于"会动态规划"
我在前 20 道动态规划题里最大的错觉是：每做完一道题，我就觉得自己掌握了动态规划，但只要题目稍微换个形式，我又立刻卡住。
后来我意识到问题出在哪——我一直在背答案，没有理解"状态"和"阶段"这两个概念。状态指的是问题在某个时刻的"快照"，比如背包问题中"已经处理完前 i 件物品、当前背包容量为 j"就是一个状态；阶段则是状态推进的顺序，通常用循环变量 i 来体现。动态规划的过程，就是按照阶段从前往后，逐个状态计算并保存结果，最后从保存的结果中取出答案。
把概念落实到这种程度以后，我才真正开始具备"拿到新题也能试着想出状态定义"的能力。所以这篇学习笔记里，我也会刻意在每个题目上先讲"怎么想到状态是这么定义的"，再讲方程和代码，而不是直接甩一个方程让你背。
2. 从斐波那契数列开始建立状态转移的直觉
2.1 暴力递归为什么又慢又废
说动态规划之前，必须先看它的反面教材：暴力递归。斐波那契数列的定义本身是递归式的，f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)，所以最直观的写法就是直接翻译定义：
def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)这段代码在 n=40 左右就开始明显卡顿，n=50 的时候基本等不出结果。我刚开始学的时候不理解，明明 n 只有 50，为什么这么慢？后来把递归调用树画出来就懂了：fib(50) 需要调 fib(49) 和 fib(48)，fib(49) 又需要调 fib(48) 和 fib(47)，也就是说 fib(48) 被重复计算了两次，fib(47) 会被重复计算三次，越靠前的项被重复计算的次数越多，整体复杂度是 O(2^n)，这个增长曲线极其恐怖。
从递推公式就能看出，斐波那契数列完美命中动态规划的"重叠子问题"特征：同一个子问题在递归树里被反复求解，而这些子问题的数量其实只有 n+1 个，我们却付出了指数级的时间代价。
2.2 记忆化递归：加一个缓存就够用
既然慢的原因是重复计算，那解决方法就非常直接：把已经算过的结果存下来，下次再需要同一个子问题时，直接从缓存里取，不用重新递归。
memo = {} def fib_memo(n): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib_memo(n-1) + fib_memo(n-2) return memo[n]这种方式叫自顶向下的记忆化递归，它保留了递归的代码结构，只是用哈希表做了一层缓存。改动只有几行，但复杂度立刻从 O(2^n) 降到了 O(n)。我这里用的是全局字典做缓存，实际写代码时更推荐用 Python 的functools.lru_cache装饰器，或者直接传入一个数组，避免全局变量带来的副作用。
记忆化递归是理解动态规划非常好的跳板，因为它的思路非常直观：问题本身还是那个递归问题，只是我们把重复劳动省掉了。从记忆化递归转到下文要说的迭代递推，只需要再往前跨一步。
2.3 迭代递推：把递归栈换成 for 循环
记忆化递归虽然时间复杂度已经达标，但递归本身有函数调用开销，递归深度过深时还可能撑爆栈。此时可以改为自底向上的迭代写法：
def fib_iter(n): if n <= 1: return n dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]用一个长度为 n+1 的数组 dp 记录每一个子问题的答案，然后从前往后循环计算。这就是标准动态规划的形状：先确定状态（dp[i] 表示第 i 项的值），再确立阶段顺序（从 0 扫到 n），最后每步用状态转移方程算出当前位置的值。
还能进一步优化空间：由于 dp[i] 只依赖前两个数，根本不需要保存整个数组，只用两个变量滚动更新即可。这就是"滚动数组"思想的雏形，我们在背包问题里还会再遇到它。
2.4 状态转移方程到底长什么样
很多人第一次学动态规划，被"状态转移方程"这个名词吓到，觉得得是高等数学里那种偏微分方程才有资格叫"方程"。其实在动态规划语境下，方程就是一个朴素的条件等式，比如：
dp[n] = dp[n-1] + dp[n-2]它的作用就是把"未知的当前状态"用"已知的更小状态"表示出来。斐波那契的方程之所以简单，是因为它的子问题划分方式太明显了；真正的难点在于遇到实际问题时，状态怎么定义、方程怎么推导。从我刷题经验来看，绝大多数动态规划题的瓶颈不在代码，而在"能不能写出这个方程"。
3. 背包问题：最常见的动态规划考场主角
3.1 01背包问题的原始场景和状态定义
爬楼梯是理解动态规划的预热菜，背包问题才是真正的正餐。01背包的原题描述非常经典：有 n 件物品和一个容量为 W 的背包，每件物品有重量 w[i] 和价值 v[i]，每种物品最多选一件，求背包能装下的最大总价值。
我第一次拿到这道题，第一反应是"贪心"，觉得可以先按性价比排序，优先装单位重量价值最高的物品。这个思路在部分测试用例下确实能过，但只要稍微构造一个反例，比如"超大价值但超重的物品 + 恰好能塞满的多个小物品"，贪心立刻翻车。这道题需要的是对所有物品做全局统筹，属于典型的"不能局部决策，必须全局搜索"的问题。
01背包的状态定义是学习动态规划的关键一步。我第一次看到官方解法时，对dp[i][j]的含义理解了很久。它定义为：从前 i 件物品中选取若干件，放入容量为 j 的背包，能获得的最大价值。这里的 i 表示"只考虑前 i 件物品"这个阶段，j 表示"背包容量"这个维度。有了这两维，每个状态都能唯一描述一个子问题。
3.2 状态转移方程的推导过程
现在重点来了：dp[i][j]怎么从前面的状态推导出来？
处理第 i 件物品时，只有两种决策：选它或者不选它。
- 如果不选第 i 件物品，那么问题退化为"从前 i-1 件物品中选，放入容量为 j 的背包"，当前最优值就是 dp[i-1][j]。
- 如果选第 i 件物品，那么前提是背包容量 j 至少能装下 w[i]，并且放入后剩余容量为 j-w[i]；此时总价值等于"从前 i-1 件物品中选，放入容量为 j-w[i] 的背包的最大价值"再加上 v[i]，也就是 dp[i-1][j-w[i]] + v[i]。
两种情况取最大值，得到方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])这个方程的推导过程其实非常朴素：面对一件物品，你只有"要"和"不要"两个选项。动态规划解决的就是这样的问题——每一步的决策空间非常有限，但组合起来数量庞大。
3.3 边界条件和初始化
写代码之前，必须先确认边界条件。dp[0][j] 表示"前 0 件物品"（即一件都不选）能达到的最大价值，无论背包容量多少，价值都是 0。所以初始化时把整个 dp 数组初始化为 0 即可。
def knapsack_01(n, W, weights, values): dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): w = weights[i-1] v = values[i-1] for j in range(1, W + 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][W]注意这里遍历容量 j 时，我写的是从 1 到 W。容量为 0 时装不下任何物品，dp[i][0] 恒为 0，所以从 1 开始没有影响。每次循环还要判断 j 是否大于等于 w，否则会数组越界访问负索引，这是新手最容易踩的 bug。
3.4 滚动数组优化：从二维到一维
二维 dp 数组的时间复杂度和空间复杂度都是 O(nW)，在数据规模较大时，空间开销可能超标。仔细观察状态转移方程会发现，dp[i][j]只依赖dp[i-1][...]，也就是说，第 i 层的计算只与上一层的值有关，跟更早的层毫无关系。所以完全可以用一维数组滚动更新，每轮循环前数组存的是上一层的数据，循环后用当前层覆盖它。
def knapsack_01_optimized(n, W, weights, values): dp = [0] * (W + 1) for i in range(1, n + 1): for j in range(W, weights[i-1] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i-1]] + values[i-1]) return dp[W]这里有一个极其关键的细节：内层循环必须倒序遍历容量 j。原因是为了保证每件物品只被选一次。如果正向遍历，dp[j-w[i]] 可能是本轮已经更新过的值，等于在同一个物品身上又叠加了一次，就变成"每件物品可以无限取"，也就是完全背包的逻辑。反过来，倒序遍历让 dp[j-w[i]] 仍然是上一轮计算出的旧值，从状态上保证了最优解中同一件物品最多出现一次。我在初学阶段经常在这个顺序上翻车，每次都是 AC 不了才发现是遍历方向写反了。
3.5 完全背包与01背包的区别：正序遍历的原因
完全背包问题描述几乎一样，唯一的区别是每种物品可以取无限件。这时候代码反而更简单：只要把 01 背包一维优化版本里的倒序遍历改成正序遍历，就变成了完全背包的解法。
正序遍历的逻辑可以这样理解：当内层循环从容量小的一端走向大的一端时，dp[j-w[i]] 已经被本轮更新过，已经包含了"再取一件当前物品"的可能性，所以一件物品可以重复叠加，符合"无限取值"的约束。这个细节只需要一行代码的改动，但背后的语义差别非常大。我在实际面试中发现，很多候选人能背下 01 背包的代码，但当面试官问"为什么完全背包要正序遍历"的时候，却答不上来。所以理解"遍历顺序背后的含义"比背代码重要得多。
顺带一提，热搜词里提到的 KMP 算法中的 next 数组，虽然不属于动态规划的经典例题，但它同样体现了"用小状态推大状态"的递推思想。如果你学完动态规划再回头看 KMP 的 next 构造过程，会有一种"原来之前见过的很多算法，底层都有类似骨架"的感觉。
4. 快速判断一道题能不能用动态规划的三个信号
4.1 信号一：题目在问"最多、最少、多少种方案"
动态规划最适合解决的问题，通常是求最优解或者方案计数，比如"最大子数组和""最长公共子序列""最少硬币数""共有多少条路径"。这些问法的共同点是：结果是一个数值，而且这个数值可以通过子问题的结果递推出来。
有一个很直观的判断方式：如果题目问的是"最大值/最小值/方案数"，而且每一步都有多种选择，那恭喜你，动态规划大概率是正解方向。比如"从左上角到右下角，每次只能向下或向右，一共有多少条不同路径"，这个"多少种方案"的问法就强烈指向动态规划，而不是深度优先搜索去穷举——虽然 DFS 也能做，但复杂度是指数级的。
4.2 信号二：大问题的解依赖小问题的解
这个信号看起来像废话，但实际操作中很多人会忽略。我见过一些同学拿到题之后，第一反应是列表格、套公式，结果发现完全套不进去，就是因为那道题根本不存在清晰的"小问题到大问题的递推链条"。
一个比较靠谱的检验方法是：写一个递归表达式试试。比如最长递增子序列，可以定义 dp[i] 为"以第 i 个元素结尾的最长递增子序列长度"，然后 dp[i] 等于遍历前面所有 j < i 且 nums[j] < nums[i] 的元素，取 max(dp[j] + 1)。能写出这种"当前状态依赖前面某个状态"的表达式，说明递推关系是存在的。如果尝试半天写不出这种关系，那就要考虑是不是该用回溯、贪心或者其他思路了。
4.3 信号三：子问题之间存在重叠
这一点是把动态规划和分治算法区分开的关键。分治算法（比如归并排序、快速排序）也会把大问题拆成小问题，但每个小问题基本上是独立求解的，没有大量重复；动态规划拆出来的小问题之间却高度重叠。
判断有没有重叠，最直接的方法还是回到递归：画递归调用树，看同一个参数被重复调用了多少次。比如爬楼梯的递归树，同一个 f(k) 会被很多不同的路径走到，这就是重叠。如果某个问题的递归树里每个节点都只出现一次，那就没有重叠子问题，动态规划省不掉任何时间，硬上反而可能更慢。
4.4 拿几个经典题做判断练习
我刷题时会刻意做"题型归类"训练，看到一道题先别急着写代码，而是先判断它属于哪类：是动态规划，还是贪心，还是回溯，还是图算法。
- 爬楼梯、矩阵路径、不同路径：典型的动态规划，状态和方程都很直观。
- 找零钱的最小硬币数：如果硬币面额任意，贪心不保证最优，用动态规划做全局最优。
- 最长回文子串：可以用中心扩展法，也可以用动态规划定义 dp[i][j] 表示 s[i:j] 是否为回文。
- 求一组数能否分割成两个和相等的子集：这是 01 背包的变体，状态是"是否存在某个子集和为 target"。
做这种判断练习的时间花得很值，因为面试中最大的不确定性恰恰在于"这道题到底考什么"。有时候面试官不会直接告诉你这题要用动态规划，而是让你自己根据题目特征去识别。练多了以后，你拿到题目，会自动在脑子里过一遍这几个信号，比盲目刷题高效得多。
5. 学习动态规划最容易踩的四个坑
5.1 坑一：状态定义太粗或太细
状态定义是动态规划的灵魂，但初学者经常把它定义得不是太粗就是太细。
太粗的典型例子：用 dp[n] 表示"前 n 个元素的最大值"，但遇到需要考虑连续子数组的情况，这个定义根本推不出转移方程，因为 dp[n] 无法区分"包含第 n 个元素的连续子数组"和"不包含第 n 个元素的连续子数组"。而最大子数组和这题，恰恰需要后者作为状态：dp[i] 定义为"以第 i 个元素结尾的连续子数组的最大和"，转移方程 dp[i] = max(nums[i], dp[i-1] + nums[i]) 才写得出来。
太细的例子则相反，有人会把状态定义得特别复杂，比如加上了题目里根本不需要的记录维度。状态定义的原则应该是"不多不少刚好够用"。多加一个维度，要么导致空间复杂度爆炸，要么让你的转移方程变得极其难写，所以定义状态时要反复问自己：这个信息真的影响后续决策吗？如果不影响，就不要放进状态里。
5.2 坑二：边界条件没有单独确认
动态规划代码写完之后最怕的不是逻辑错误，而是"答案在边界处算错"。比如求最小路径和时，dp[0][0] 应该初始化成 grid[0][0]，而不是 0；比如爬楼梯问题时，f(1)=1，f(2)=2，而不是 f(0)=0，f(1)=1。很多题目因为边界条件不同，最终回答会差一个常数甚至直接错误。
我现在做题的习惯是，写完状态转移方程之后，第一时间把 i=0、j=0、数组为空、只有一个元素这些边界情况分别在纸上推一遍，确认初始化代码符合实际意义。这个习惯帮我省去了大量调试时间，也让我在面试现场不用反复试错，直接一次性把代码写对。
5.3 坑三：遍历顺序写反（正序/倒序混淆）
前面提到 01 背包和完全背包的差别只有一行代码，正序还是倒序遍历直接决定了题目性质，这是我踩过最深的一个坑。后来我做了个总结：
- 如果每个物品最多选一次，内层循环用倒序。
- 如果每个物品可以选无限次，内层循环用正序。
- 如果问题实际是"二维费用"或者"分组背包"等变体，要在标准模板基础上重新推导遍历顺序，而不是盲目套用。
这个坑不只出现在背包问题里。多维动态规划中，如果状态转移既依赖更小的状态又依赖本维度更新的状态，遍历顺序就非常敏感，写反了会让结果彻底错乱。遇到这种情况，我的建议是：先在草稿纸上写上几个具体数值，手动模拟一遍循环流程，确认当前状态依赖的那个状态确实已经被计算过，再开始写代码。
5.4 坑四：拿到题就想着套模板，而不是先找状态
这是最致命的一个坑，也是我从大量刷题中总结出来的深层教训。动态规划的经典题目确实有模板可循，比如背包有背包模板、最长公共子序列有 LCS 模板，但真实题目往往不会长得和模板一模一样，而是在状态上做了各种变形。遇到变形题，如果脑子里只有模板的代码，没有"自己设计状态"的能力，题目稍微一变就卡死。
我自己的对策是：拿到一道题，先不写代码，先用中文把状态定义写出来。比如"dp[i][j] 表示考虑前 i 个物品、背包剩余容量为 j 时最多能装的价值"——先把这个句子写清楚，再思考转移方程，最后写代码。状态定义一旦准确，后面的代码往往只是机械翻译；状态定义如果模糊，代码一定会写歪。
我个人学习动态规划走到现在，最大的体会是：这是一个需要"看懂 + 动手 + 复盘"三件套的知识板块。看十篇教程，不如自己亲手推导一个状态转移方程；刷一百道题，不如把每道题的状态定义和边界条件在纸上认真写一遍。动态规划的套路说多不多，说少不少，核心其实就那句：把大问题拆成小问题，小问题答案存起来，用已知推未知。当你发现一道新题能自己顺利写出状态转移方程的时候，那种感觉真的非常值得。
