如果你刷过一段时间的算法题一定遇到过这样的场景一道题用暴力枚举写出来小数据几毫秒出结果数据规模一上来直接超时到怀疑人生。旁边的同学轻飘飘一句“这题动态规划一下”剩下你对着题目发呆想问“状态是什么”“转移怎么写”却不好意思开口。动态规划是整个算法学习里绕不过去的一座山也是算法工程师面试中出镜率最高的一类题。这篇内容我想用自己做过几年算法题、也面过别人的视角把动态规划从“背模板”里解放出来讲清楚它到底在解决什么问题、怎么从一个会超时的暴力递归一步步改成DP、实操时最容易踩哪些坑以及顺着它怎么够到状态压缩、树形DP这些进阶模型。无论你是刚接触数据结构与算法的新手还是正在洛谷题单上吭哧吭哧刷题的人这篇文章应该都能给你一些新东西。1. 动态规划的本质理解它不是模板是决策过程的建模1.1 动态规划到底解决了什么问题先看最朴素的定义动态规划Dynamic Programming简称DP是一种把原问题拆成子问题通过解决子问题并记录结果来避免重复计算的方法。但这句话太空了。我更愿意把它理解成当一个决策问题存在“重叠子问题”和“无后效性”两个条件时我们可以用一张表把已经算过的答案存下来用递推的方式从最简单的状态一路推到目标状态。这张表就是DP表这套从简单到复杂的推法就是动态规划。斐波那契数列是最经典的例子。暴力递归写法是def fib(n): if n 2: return n return fib(n - 1) fib(n - 2)如果你画一下递归调用树fib(5) 会调用 fib(4) 和 fib(3)fib(4) 又调用 fib(3) 和 fib(2)同一个 fib(3) 被重复算了好几次。n40 的时候递归次数已经呈指数增长肉眼可见地卡顿。但如果开一个数组把每个 fib(i) 都存下来整体就变成一层线性循环。这个“避免重复计算”的价值就是DP最直接的收益。不过要注意不是所有能拆分的问题都适合DP。分治算法比如归并排序也是拆子问题但子问题之间基本不重叠每个子问题独立解决完再合并不存在重复计算。动态规划面对的则是子问题大量重叠的场景所以才有“记录下来”的必要。另外DP还要求决策关系是单向的、无环的后面的状态只依赖前面阶段的结果不会反过来影响之前的决策这就是所谓的“无后效性”。这两个条件是判断一道题能不能DP的第一个筛子。1.2 从暴力枚举到DP的思维递进很多人一开始学DP觉得难是因为题目看起来像搜索、又像贪心最后才想到DP。这里我建议你把“从暴力枚举到DP”的转变过程完整走一遍而不是直接背状态。暴力枚举的本质是“把所有可能都试一遍”。拿爬楼梯举例一次可以爬1级或2级问爬到第n级有多少种方法。暴力枚举就是把所有走法列出来然后数一数。可爬到30级时走法数量本身就已经爆炸了。这时你观察会发现爬到第n级的方法数只和“到第n-1级的方法数”“到第n-2级的方法数”有关因为最后一步不是跨1级就是跨2级。于是f[n] f[n-1] f[n-2]这就是“从最后一步反推”的思维方式也是DP最常见的建模切入点想想我要得到答案最后一步有哪些可能每一种可能把问题变成了哪个更小的子问题。这个思路能套到大量题型里最长公共子序列想最后两个字符是否相等0-1背包想最后一个物品装不装区间DP想最后合并的是哪两块。牢牢记住“从最后一步切入”这个思路比记住任何一个具体的例题都重要。它本质上是在做一件事把一棵庞大的递归树裁剪成一条有依赖顺序的计算链每个节点只算一次。1.3 动态规划三大要素状态、转移、边界接触过DP的人都听过“状态”“转移方程”“边界条件”这三个词。我按自己的理解拆开说一下状态DP表里每一个格子代表什么含义。比如 f[i] 表示“爬到第i级楼梯的方案数”。状态是整个DP的灵魂状态定错了后面全废。转移方程相邻状态之间的关系。它描述一步决策如何把规模更小的子问题组合成当前问题的答案。转移方程必须覆盖所有情况不能漏也不能因为状态定义不清导致重复计算。边界条件递推起点的值。比如爬楼梯 f[1]1、f[2]2或者干脆约定 f[0]1。边界错了整个递推从起点就歪了。我常用一个生活化类比来理解DP动态规划就像读一本有章节指引的故事书。你先读完最简单的第一章边界每读完一章就把结论记在笔记本上状态存储下一章只需要参考笔记本上几个之前章节的结论就能推出状态转移。如果没有笔记本每章都从第一页重新读起那就是暴力枚举有了笔记本每一章只读一遍就能顺着往后推进这就是动态规划。2. 从暴力递归到DP的四步转换法手把手把“递归超时”改造成“递推通过”2.1 第一步先用暴力递归把问题写出来很多教程一上来就教递推忽略了更自然的起点先把递归写出来。递归的代码结构和题目描述最贴近能帮你快速明确“子问题到底是什么”。我写DP题的习惯是先按题目要求直接写一个递归函数参数就是状态里需要区分的信息返回值就是答案。拿爬楼梯来说def climb(n): if n 2: return n return climb(n - 1) climb(n - 2)递归版本虽然会超时但它暴露出两个重要信息参数 n 就是状态两个递归分支就是转移的雏形。把递归函数里那些“重复计算的调用”变成“查表”就是DP的本质改造。这一步不用想优化只要能跑通小数据、确认逻辑正确就行。写递归时有几个小技巧参数尽量少越少越容易看清状态依赖关系递归出口一定要写在最前面如果返回值同时受多个参数影响别害羞把所有必要参数都写进函数签名里。信息缺失比参数多更可怕因为转移会无从下手。2.2 第二步加备忘录改成记忆化搜索递归慢是因为重复计算。最简单粗暴的优化就是缓存算过的不再算直接查。这就是记忆化搜索。把爬楼梯改成带缓存的递归from functools import lru_cache lru_cache(None) def climb(n): if n 2: return n return climb(n - 1) climb(n - 2)或者手动开一个 memo 数组算之前看一眼算完存一下。记忆化搜索是“自顶向下”的DP从大问题出发递归到小问题再回溯组合答案。它的优势是思维负担小递归骨架不用变只加缓存。但是递归调用本身有栈开销极端大数据下可能爆栈而且自顶向下的写法通常不方便做空间优化。所以记忆化搜索适合“快速验证思路”和“状态转移方向难确定”的题真正要追求效率时还是要落到底部递推。2.3 第三步改成自底向上的递推自底向上的思路是既然大问题依赖小问题那就从最小的边界开始一层层往上算。还是爬楼梯n int(input()) f [0] * (n 1) f[1] 1 f[2] 2 for i in range(3, n 1): f[i] f[i - 1] f[i - 2] print(f[n])对比递归版本你会发现递归里的 climb(n-1) 变成了数组里的 f[i-1]递归出口变成了数组初值递归调用顺序变成了 for 循环从3到 n 的递推。整个过程就是把“函数调用”换成“查表、填表”。这里最容易犯错的是填表顺序。核心原则是算 f[i] 时用到的所有 f[j] 都必须已经算好。大多数一维题从小到大循环就行但有的题不是简单从小到大比如区间DP要按“区间长度”从小到大的顺序树形DP要先递归子树再回溯更新。所以不要机械背循环方向要看清状态依赖方向。这一步走通了你已经写出标准DP了。2.4 第四步空间优化——滚动数组与降维动态规划的空间复杂度经常还能再砍。如果一个状态只依赖前面有限个状态就不必保存整张表。爬楼梯只需要两个变量滚动a, b 1, 2 for i in range(3, n 1): a, b b, a b滚动数组的意义不只是省几个字节有时还能帮你发现时间优化空间。比如后面要讲的0-1背包一维化就是在滚动数组基础上通过逆序遍历区分“旧值”和“新值”避免覆盖污染。我一直觉得“能不能把二维滚成一维”是判断一个人DP理解是否到位的好问题。你在面试里能主动讲清楚为什么从二维降到一维、为什么遍历方向变了会给面试官留下非常扎实的印象。3. 核心细节解析状态设计、转移推导与初始化的实操要点3.1 状态设计先把维度定下来状态设计没有万能公式但有可循的路径。我一般按“问题里有几个关键变量”来定维度一个变量比如“前i个物品”“长度为i的序列”——一维DPf[i] 通常表示前i个元素的最优值或方案数。两个变量比如“前i个物品里选背包容量为j”——二维DPf[i][j]。如果还有额外限制比如“必须恰好选k个”就得加维度变成 f[i][j][k]。每个维度都要有明确的含义和取值范围。常见的坑是维度定义太模糊导致转移时不知道从哪些状态来。我建议状态写好之后先自己翻译一句人话比如“f[i][j] 表示处理完前i个物品、背包容量为j时能获得的最大价值”。如果这句话说不通状态十有八九有问题。状态设计的本质是“只保留做最后一步决策所需要的最小信息集合”。比如最长递增子序列为什么必须定义成“以第i个元素结尾”而不是“前i个元素”因为如果不记录结尾元素就不知道后续能否继续接着增长。这就是状态里的信息必要性。3.2 转移方程如何确保不漏不重写转移方程的核心技巧我总结成三步把当前状态 f[i] 看成“还没做最后一步决策时的各种可能集合”思考最后一步有哪些选择。对每一种选择把问题退化成一个或多个规模更小的子问题。根据题目要求取 max、min 或求和拼出转移方程。以最长递增子序列为例f[i] 表示以第i个元素结尾的最长递增子序列长度。最后一步是“上一个元素是谁”可以是前面任意一个值比 a[i] 小的 j于是f[i] max(f[j] 1)其中 j i 且 a[j] a[i]这个转移不会漏因为所有可能的 j 都枚举了不会重因为最大值重复不影响结果。如果题目要求“方案数”就要小心是否把同一种序列算了多遍这通常涉及状态语义的精细化。还有一个点是“合法状态”与“非法状态”的区分。比如背包求“最多能装多少”和“恰好装满”的区别本质就是初始化和非法状态的不同。求最多能装时 f 数组全初始化为0装不下的状态天然是0求恰好装满时 f[0]0其他初始化为负无穷表示“恰好装满这些容量目前不可行”。这个细节我后面在背包部分还会重点强调因为太多人在这里翻车。3.3 边界与初始化事故高发区我见过无数人转移方程写得没问题代码却跑不出正确答案最后发现是初始化错了。初始化不是随便填一排0而是在定义“子问题的基准答案”。几个常见规则求方案数边界通常置为1比如 f[0] 1 表示“空方案也是一种方案”然后从f[0]开始累加。求最大值边界通常置为0非法状态置为负无穷-INF比如 -1e9避免被 max 选中。求最小值边界通常置为0非法状态置为正无穷INF比如 0x3f3f3f3f避免被 min 选中。注意下标偏移如果状态里出现 i1 访问 f[i-1]循环得从合适的位置开始如果 f[0] 是“空状态”它的含义要想清楚。用 C 的话memset 的字节值有讲究0x3f 是一个很好用的“较大值”两个 0x3f3f3f3f 相加也不会溢出 int。但它不等于“无穷大”处理负无穷时要小心。用 Python 的话初始化列表时多确认一次长度够不够不要因为疏忽把 dp 数组长度设成 n-1。4. 经典模型实战拆解线性DP、背包DP与区间DP4.1 线性DP从最长递增子序列看状态与二分解法LIS 应该是一维DP里最经典的题目也是洛谷动态规划题单里必有的入门题。朴素DP上面写过再贴一次完整可运行的写法n int(input()) a list(map(int, input().split())) f [1] * n for i in range(n): for j in range(i): if a[j] a[i]: f[i] max(f[i], f[j] 1) print(max(f))这是 O(n^2) 的解n5000 以内都能跑。如果 n1e5就得换思路维护一个 tails 数组tails[k] 表示长度为 k1 的递增子序列中最小的结尾元素。遍历每个数时用二分查找找到第一个大于等于它的位置并覆盖。这个优化的核心理解是对于长度相同的递增子序列结尾元素越小越好这样后续越容易接上更长的序列。这个思想非常实用很多看起来像LIS的题都能这样转化。实际操作中我建议初学者先写朴素版把 f 数组打印出来看几遍确认自己理解了“以第i个元素结尾”这个状态的含义再去碰二分优化。直接背二分版代码很容易出细节错误比如二分边界是“大于等于”还是“大于”差一个等号最终答案就可能算错。4.2 背包DP0-1背包的一维化与遍历顺序背包问题是动态规划最重要的模型之一“0-1背包”在面试和竞赛里出现频率极高。先上二维版本状态f[i][j] 表示前i个物品总重量不超过j时能获得的最大价值。转移最后一个物品拿或不拿。不拿就是 f[i-1][j]拿就是 f[i-1][j-w[i]] v[i]。核心代码for i in range(1, n 1): for j in range(1, W 1): if j w[i]: f[i][j] max(f[i - 1][j], f[i - 1][j - w[i]] v[i]) else: f[i][j] f[i - 1][j]一维优化版f [0] * (W 1) for i in range(1, n 1): for j in range(W, w[i] - 1, -1): f[j] max(f[j], f[j - w[i]] v[i])关键点在于 j 必须从大到小遍历。为什么因为 f[j - w[i]] 这里需要用“上一轮i-1的结果”。如果正序从小到大更新那么 f[j - w[i]] 可能已经被本轮i更新过了相当于同一个物品被拿了好几次0-1背包就会悄悄变成完全背包。逆序则保证每次查到的都是更新前的旧值。如果题目是每个物品可以无限拿的完全背包遍历顺序就要反过来从小到大。还有多重背包、分组背包等变体都是在这些逻辑上做更进一层。但不管怎么变“先枚举物品再枚举容量容量是逆序还是正序”永远是核心判断题。4.3 区间DP从石子合并看区间划分区间DP的典型特征是问题是在一个区间上做合并或划分状态常常设计成 f[i][j] 表示区间 [i, j] 的最优解。石子合并是经典题有n堆石子排成一排每次只能合并相邻两堆合并代价为两堆石子数之和问最小总代价。状态定义为 f[i][j] 把第i堆到第j堆合并成一堆的最小代价。最后一步一定是在某个位置 k 断开把 [i, k] 和 [k1, j] 先分别合并成两堆再合并这两堆f[i][j] min(f[i][k] f[k1][j] sum(i, j))这里最大的坑是循环顺序。如果按 i 从小到大、j 从小到大去枚举会出现计算 f[i][j] 时 f[k1][j] 还没算完的情况。正确做法是外层枚举区间长度 len内层枚举左端点 i保证每个更短的区间都已经算出来。我第一次学区间DP时也卡在这里后来才理解这不是玄学而是依赖关系决定的区间越大它依赖的小区间必须先算完。环形版本的变体通常是把原数组翻倍再按线性处理本质上还是区间DP。5. 完整实操实录零钱兑换从暴力到AC全过程5.1 题目分析与暴力递归初探理论说再多不如完整跑一遍。零钱兑换LeetCode 322是我认为最适合用来演示全过程的题因为它能清楚展示“暴力递归 → 记忆化 → 自底向上 → 优化”的完整演进而且它就是面试高频题。题目大意给定不同面额的硬币 coins 和一个总金额 amount计算凑成总金额所需的最少硬币个数。如果没有组合能组成返回 -1。每种硬币数量无限。先写成暴力递归定义 f(amount) 为凑出 amount 的最小硬币数。最后一步是“选择一枚硬币 c”问题就变成 f(amount - c)所以f(amount) min( f(amount - c) for c in coins if amount c ) 1边界f(0) 0。直接递归会大量重复计算 amount 的子问题小金额可能还好amount 一大立刻超时。我建议写算法题都先走这一步你会在递归函数里清晰地看到状态参数、分支条件和边界后面改写成DP表会非常顺。5.2 状态定义与DP表填充把递归改成自底向上的DP表def coinChange(coins, amount): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! INF else -1逐行看这个代码dp[i] 初始化为 INF表示“凑出 i 元目前还没找到有效方案”。dp[0] 0 是整个递推的地基。外层遍历所有金额从 1 到 amount内层遍历每个硬币。因为硬币数量无限这里金额从小到大正序更新等价于完全背包。最后如果 dp[amount] 仍是 INF返回 -1。这个代码已经是完整可提交的AC解法了。时间 O(amount * len(coins))空间 O(amount)。能优化空间吗这个维度只有一个已经是线性空间不太能再压了。但如果你写的是二维常规版可以从二维滚到一维这种经验值得积累。5.3 调试技巧与小样例推演拿到代码别急着交先手工推一遍小数据比如 coins [1, 2, 5], amount 11。dp[1] min(dp[1], dp[0] 1) 1用1元。 dp[2] min(dp[1] 1 2, dp[0] 1 1) 1用2元。 dp[3] min(dp[2] 1 2, dp[1] 1 2) 221。 ……推到 dp[11] 3即 551。我调试DP时最常用的一招在循环里 print 中间 dp 数组或者只打印几个关键位置的转移过程。如果答案不对先查边界再手推几个小用例最后怀疑初始化是否污染。这个排查顺序能解决九成的问题。其实很多所谓“没想到”的DP细节错误本质上都是小样例没推透。5.4 变体扩展方案数与组合、排列的区别零钱兑换有很多变体最常见的是“返回方案总数”。求方案总数时初始化 dp[0] 1其他 dp 为0转移用加法dp[0] 1 for i in range(1, amount 1): for c in coins: if i c: dp[i] dp[i - c]但这里有一个经典的顺序问题如果认为 [1, 2] 和 [2, 1] 是两种方案上面的写法会包含两者因为金额自外层、硬币自内层相当于统计的是“排列”。如果想统计“组合”即认为 [1, 2] 和 [2, 1] 是同一种方案就要把硬币放在外层、金额放在内层dp[0] 1 for c in coins: for i in range(c, amount 1): dp[i] dp[i - c]我建议你亲手跑一遍对比结果这个差异一旦自己踩过就永远记住了。理解它需要回到“状态更新顺序”的本质外层循环决定你每次新增的“决策维度”内层循环则枚举了在这个维度下的所有金额状态。6. 刷DP必踩的坑常见问题与排查技巧实录6.1 状态定义不清晰转移无从下手症状拿到题想了半天不知道 f[i] 表示什么或者状态定得太宽比如直接 f[i] 表示“前i个元素的最优解”结果转移时发现信息不够。这是初学者最容易遇到的问题。对策状态定义必须包含“做最后一步决策时所需的最小信息集合”。LIS 必须以第 i 个元素结尾因为不记录结尾元素就无法判断后续能不能继续接。做题时如果转移卡住先回头想想做最后一步时我需要知道哪些信息才能决定下一步把它们全部加进状态里。宁可多一个维度和一点空间也不要让状态信息缺失。6.2 边界与非法状态处理失误症状最小值问题初始化为0导致答案永远都是0或者方案数问题少了 dp[0]1答案整体差一截。对策把“边界”和“非法状态”分开想清楚。dp[0] 往往是专门为递推服务的“空状态”要单独确认语义非法状态用正负无穷表示保证不会被更新选中。我处理 min/max 时有个习惯先在注释里写清“dp[i] INF 表示目前不可达”再写代码防止自己手滑。边界条件不是靠记的是靠“代入递推的第一圈”验证的最稳妥。6.3 数组越界与下标偏移症状循环里访问 dp[i - c] 时 i - c 是负数或者 f[i-1][j-w] 数组越界。对策一种做法是在访问前判断 i c另一种是把 dp 表开大一点比如多开几个哨兵位置然后用合法的初始化兜底。遇到“前i个”和“第i个”混用下标经常差1建议全程统一语义并在注释里固定下来。用 C 写算法题时尤其要注意下标越界不一定立刻崩溃可能悄悄把相邻内存污染了最后输出一个非常诡异的大数排查起来很痛苦。6.4 无后效性问题症状状态在转移之后又会被后面的状态影响导致无论怎么调整循环顺序都对不上这种题目往往存在“循环依赖”。对策DP要求决策关系是有向无环的。如果发现需要依赖“后面的值”要么换状态定义要么用拓扑排序、搜索等其他算法。比如树上的动态规划本质上就是借助树的天然层级关系先算子树再回溯更新。这也是为什么我说动态规划不是万能的它只适合无后效性的问题。面试时能主动识别出“这题不是DP”也是一种很强的能力。6.5 空间优化带来的覆盖污染症状一维背包写了正序遍历结果同一种物品被用了多次滚动数组时两个状态互相覆盖输出结果错误。对策每次做空间优化前先想清楚当前代码需要使用“上一轮”还是“本轮”的值。需要上一轮时要么逆序更新要么用临时变量暂存。经验是一维滚动后结果不对不要靠猜先在纸上画几轮更新过程确认覆盖顺序。我把常见问题整理成一张速查表方便你快速定位现象常见原因排查方向答案偏大最大值问题初始化用了0非法状态被选中非法状态改负无穷答案偏小最小值问题初始化用了0非法状态没排除非法状态改正无穷背包数量超限0-1背包正序遍历容量容量逆序完全背包数量不够完全背包逆序遍历容量容量正序数组输出神秘大数数组越界 / 下标偏移 / 未初始化检查下标范围答案固定为某个值dp[0] 意义不清或漏初始化复核边界语义7. 动态规划的进阶方向与实际应用7.1 面试中的DP考察算法工程师面试里DP几乎是必考板块。面试官通常会观察你拿到题能不能快速识别模型状态定义讨论得是否清楚有没有空间优化意识。不会有人要求你三秒内给出最优解但很看重你把三个要素逐步分析出来的过程。我的建议是面试时先大声说思路先确认能不能暴力枚举再分析有没有重叠子问题给出状态定义并解释为什么这么定最后写转移方程时把“最后一步”的逻辑讲给面试官听。即使一时没有最优解这个思维过程本身就很加分。相反如果你上来就沉默着埋头写代码即使写对了面试官也难判断你是真的理解还是碰巧见过原题。7.2 四个扩展方向状态压缩、树形、数位、图论想进阶的话把线性DP、背包、区间DP吃透后可以按这几个方向扩展状态压缩DP当状态是集合时用二进制位表示“哪些元素已经用过”典型代表是旅行商问题。n 一般在20以内才适合复杂度 2^n * n。树形DP在树上做DP先递归处理子树再回溯合并比如树上背包、树的直径。关键是理解“自底向上的递归顺序”和“父子关系怎么贡献答案”。数位DP统计区间内满足特定数位性质的数状态通常是 pos、limit、lead_zero 等几个维度本质是带约束的数字枚举。动态规划与图论结合DAG上的最长路径、Bellman-Ford 思想以及强化学习里的价值迭代本质上都是“状态 转移 最优值”这个框架的外延只是转移方式可能有概率参与。我经常建议想系统化刷题的人去找一份结构清晰的动态规划题单按照线性、背包、区间、树形、状态压缩的板块顺序刷。不用贪多每类刷透10道比一天刷50道简单题有用得多。刷的过程也别只盯着AC把每道题的“最后一步是什么”写在笔记里年底复习时会发现知识网络自然连成了片。7.3 动态规划在现实业务中怎么用很多人觉得DP只是面试题现实业务用不上其实不然。最典型的是路径规划里的最短路径类问题从起点到终点经过若干阶段每阶段有若干选择目标是最小化总代价这就是一个天然的DP模型。资源分配问题比如给几个项目分配预算每个项目投入不同、回报不同本质就是分组背包。热词里的“车辆动态规划问题”比如如何排班、分配路线使总成本最小很多时候也是先建立状态空间再做基于DP或强化学习的策略优化。实际业务里问题规模大、约束多往往要结合剪枝、贪心近似、强化学习等手段但“状态、转移、边界”这套建模思想始终贯穿其中。就算你以后不专门做算法这套“拆解问题、定义状态、建立依赖”的思考方式对系统设计同样有启发。我个人体会是动态规划不太像“背题型”能学会的技能更像一种“拆解问题”的思维习惯。每当我拿到一道新题第一反应就是问自己“最后一步是什么”然后顺着这个思路去定义状态。刷题刷得久了你会发现很多看起来毫无关联的题最后都会落进同一个模型。你若刚接触DP别怕慢哪怕一天只吃透一题把状态、转移、边界写在纸上都比囫囵吞枣刷十题走得远。如果你已经有基础了建议挑一个之前没解出来的DP题用“递归超时 → 记忆化 → 自底向上 → 空间优化”完整过一遍那种通透感值得你亲身体验一次。