动态规划DP大概是算法学习里最劝退的名词了。我见过不少人链表、二叉树、图都能写得很溜一碰到DP就卡壳。不是他们不努力——状态、转移方程这些词背得滚瓜烂熟题目稍微换个问法就傻了。我当年也一样属于“看完题解恍然大悟合上题解一脸懵”的典型。直到有一天我想明白了一件事动态规划的本质就是把暴力搜索过程中重复计算的东西全部缓存起来仅此而已。想通这一点之后刷DP题的效率高了一大截。这篇文章会从最朴素的暴力递归讲起一步步把DP推导出来再结合线性DP、区间DP、数位DP这几类高频题型说清楚动态规划到底怎么设计状态、怎么写转移方程、怎么调bug。无论你是准备算法面试、打信息学竞赛信奥还是日常工作中遇到路径规划、资源分配、序列匹配这类优化问题这篇文章都值得你花一晚上读一遍。读完你会得到一套从读题到AC的标准流程以及我这些年用DP踩过、也看别人踩过的坑。1. 动态规划没那么玄——它就是“不带重复计算的暴力搜索”1.1 一个递归让你看见重复计算是怎么拖垮程序的所有DP的起点都是暴力递归这句话建议时刻放在心里。我们拿最经典的斐波那契数列演示这个数列的递推式是 f(n) f(n-1) f(n-2)初值 f(0)0、f(1)1。先看教科书式的递归写法def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)逻辑完全正确但性能是灾难级的。我在本地实测n40 已经需要等好几秒n50 基本是几分钟都算不完。如果用纸笔画一下递归树你会发现 f(3) 被算了两次f(2) 被算了三次这些重复的子问题导致调用次数呈指数爆炸。调用次数的总和约等于 2^(n1) 这个量级也就是说 n50 时函数会被调用上千万亿次普通机器根本跑不完。这就是动态规划要解决的第一个核心问题重叠子问题。同一个子问题被反复求解而我们完全可以只算一次然后记住它。这个思路看起来简单到不值一提但正是DP所有形态的总根源。我早期刷题有个坏毛病以为会写递归就是“高级”面试一写递归版本就自我感觉良好。面试官追问一句复杂度我说O(2^n)空气都安静了。后来我养成了一个习惯——写任何递归都要先问自己三句话有没有重复子问题重复的子问题多不多能不能加一个缓存1.2 记忆化搜索到自底向上递推两种写法其实是同一件事在递归上加缓存字典代码变成这样memo {} def fib(n): if n 1: return n if n in memo: return memo[n] memo[n] fib(n - 1) fib(n - 2) return memo[n]这个写法叫记忆化搜索本质上就是自顶向下的DP。每个子问题只计算一次时间复杂度从 O(2^n) 降到 O(n)n1000 也是毫秒级出结果。但记忆化搜索有一个实际缺陷递归深度。Python 默认递归深度大约在 1000 层左右当 n 达到几万甚至更多时就算有缓存也会先撞上 RecursionError在竞赛环境里这个坑尤其明显。所以实际刷题和面试中更多人会选择自底向上的迭代版本def fib(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这份代码里出现了DP的三大件dp 数组状态、dp[1]1初始化、dp[i]dp[i-1]dp[i-2]状态转移方程。和递归版本一比你会发现它们只是同一个思想的不同写法——自顶向下是“从需求出发往回查缓存”自底向上是“从初始条件出发一路递推到目标”。两者没有本质区别选哪个更多是工程考量。斐波那契还能继续压缩空间因为 dp[i] 只依赖前两个值用两个变量滚动即可a, b 0, 1 for _ in range(2, n 1): a, b b, a b但我建议你在初学阶段别急着这么写。空间优化是建立在状态定义和转移方程完全正确的基础上的上来就滚两个变量一旦状态不只依赖前两个值你很容易被自己闷进坑里。这个原则在后面的0-1背包里还会再次出现。2. 一道题配不配用DP看这三个特征就够了2.1 重叠子问题缓存能复用的前提第一个特征是重叠子问题上文斐波那契已经展示得很彻底。通俗地说一个规模为 n 的问题在递归拆分的过程中反复需要同一个较小规模问题的解这就是重叠。如何判断最简单的方法是画递归树看看有没有重复的子树。如果你已经把暴力递归写出来了也可以在里面加一个计数器观察同一组参数被调用了多少次。当参数组合的数量有限但总调用次数远超参数组合的数量时缓存就有意义DP就能上场。这里我想补充一个容易忽略的点重叠子问题并不要求子问题完全一模一样只要“同一组状态参数”反复出现就是重叠。比如网格路径规划里dp[i][j] 表示到达 (i,j) 的最短步数从起点到达 (i,j) 的路径可能有很多条但 dp[i][j] 这个状态只会被计算一次后续所有从 (i,j) 继续往下走的分支都复用它。这也是为什么DP能把指数级枚举压缩成多项式时间——它不是在优化“枚举”而是在消灭“重复枚举”。2.2 最优子结构与无后效性为什么“当前状态只关心结果”是铁律第二个特征是最优子结构第三个是无后效性我放在一起说因为它们本质上是DP建模的两个侧面。最优子结构的意思是整个问题的最优解可以由子问题的最优解通过一次决策组合得到。以青蛙跳台阶为例dp[i] 表示跳到第 i 级台阶的跳法数。想跳到 i最后一步无非是从 i-1 级蹦一格或者从 i-2 级蹦两格所以 dp[i] dp[i-1] dp[i-2]。这个转移之所以成立是因为我只需要知道 dp[i-1] 和 dp[i-2] 这两个“结果”至于到达它们之前具体走了哪些跳法完全不影响后续决策——这就是无后效性。历史不影响未来状态就精简了。违反无后效性的反例假设跳完某些台阶之后体力耗尽下一步必须原地休息那仅仅知道 dp[i] 就不够了你还得知道当前是否“疲惫”。怎么办把影响后续决策的历史情况塞进状态里变成 dp[i][0]不疲惫到达第 i 级和 dp[i][1]疲惫到达第 i 级转移时分别处理。你看状态设计不是拍脑袋而是分析“这个决策阶段结束后哪些信息会影响未来”。按我的刷题经验出现这三类提问时优先考虑DP求最大值或最小值求满足条件的方案总数判断可行性。如果题目要你输出具体方案路径DP也能做但要额外记录转移的来源复杂度会高一些。而看到“每次贪婪取最优”这类局部策略时先别急着写贪心想想贪心选择性质到底能不能证明这个问题留到第5章详细聊。3. 从读题到AC的标准流程以0-1背包为例跑一遍3.1 状态定义是所有DP题的灵魂0-1背包是DP里最经典的题。题意一句话N件物品第 i 件重量 w[i]、价值 v[i]背包容量 W每件物品最多选一次求能装进背包的最大总价值。第一步铁打不动地定义状态。我给所有初学者的建议是定义状态时想清楚“在做完一个阶段的决策之后哪些信息必须被记住”。对0-1背包来说做完“前 i 件物品选或不选”的决策后必须记住两件事现在处理到哪一件了用 i 表示背包还剩多少容量用 j 表示。所以状态定义为 dp[i][j]前 i 件物品中做选择、放入容量为 j 的背包能获得的最大总价值。有人会问那“已经选了哪些物品”要不要记不需要因为我们只在乎总价值最大不关心具体选了谁而且后续决策只受“剩余容量”影响和已选物品列表无关。把这个想清楚状态定义就不会冗余。很多DP写不出来往往不是状态太少而是状态该压缩的维度没压缩、该保留的信息没保留。3.2 转移方程的来源选还是不选这就是那个动作有了状态定义下一步是思考第 i 件物品来了有哪几种动作不选容量不变价值继承 dp[i-1][j]。选前提是 j w[i]容量被占用 w[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])这个转移方程看起来简单但它背后是0-1背包的核心机制——每件物品的“选”或“不选”构成一次二进制决策。理解了它后面的多重背包限制选取次数、完全背包不限次数、分组背包每组最多选一个都是在“选”这个动作上扩展策略方程骨架不变。我常跟别人说写转移方程时先在纸上把“每个状态有哪些可选动作”列出来再用 max/min/累加把它们组合起来。把动作梳理清楚方程自然就出来了。反过来先背方程再套题很容易在题目变形时卡壳。3.3 初始化和遍历顺序决定你debug到几点初始化是很多人的翻车点。对上面的二维DPdp[0][j] 0因为0件物品时不管容量多大价值都是0。这个写法看似平凡但有一个小技巧对任何DP题都通用初始化前先回答“下标为0的状态在语义上是什么”。如果答案是“空集”那价值为0通常是对的但换到组合计数题时“空集方案数”常常是1而不是0第6章会详细讲语义不同答案就不同。遍历顺序方面二维写法里外层循环遍历物品 i内层循环遍历容量 j顺序正倒都行因为 dp[i] 行的计算只依赖上一行 dp[i-1] 的数据二维数组把两个阶段的答案隔离开了。真正需要警惕的是下面3.4节空间压缩后的顺序。为了让你能亲手验证我给一组具体数据N4w[2,1,3,2]v[4,2,3,6]W5。手动填一遍二维表dp[4][5] 应该等于12选1号、2号、4号物品总重量2125总价值42612。如果你算出别的数多半是初始化或转移时边界没处理好。3.4 空间压缩滚动数组到底在压缩什么二维DP的缺点是内存占用 O(NW)当 N 和 W 都到几千上万时内存可能吃紧。观察方程 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])你会发现第 i 行只依赖第 i-1 行更早的行完全用不到了。于是可以把二维压缩成一维只保留“上一状态”的一行数组dp [0] * (W 1) for i in range(n): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])重点是内层循环必须从大到小。原因是一维数组在更新时dp[j-w[i]] 如果先被本轮更新过就相当于这一行里已经包含了第 i 件物品再叠加一次就会把同一件物品装两遍。从后往前更新保证计算 dp[j] 时用到的 dp[j-w[i]] 还是上一轮的旧值。空间压缩的意义不只是省内存。在面试里能写出滚动数组通常说明你对状态依赖关系理解到位是明显的加分项。但我仍然要提醒初学者如果你对转移方程还没完全吃透先写二维验证正确后再压缩。一次就写一维版本状态错了既要找逻辑错误又要找顺序错误难度翻倍非常不划算。4. 几类高频DP题型的通用套路4.1 线性DP最长递增子序列的两种状态设计线性DP的“线性”指的是状态沿着序列下标推进。最典型的题是Longest Increasing SubsequenceLIS给定数组 nums求最长严格递增子序列的长度子序列不要求连续只要求顺序不变。经典DP解法的状态定义dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。转移时枚举 j i如果 nums[j] nums[i]就能把 nums[i] 接到以 nums[j] 结尾的序列后面所以 dp[i] max(dp[i], dp[j] 1)。最后答案取所有 dp[i] 的最大值。时间复杂度 O(n^2)写成代码是这样n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这里有两个细节值得说为什么是“以 nums[i] 结尾”而不是“前 i 个元素中的最优”因为递增子序列的扩展严格依赖最后一个元素的大小不记录结尾元素转移时就不知道当前元素能不能接上去。还要注意初始化 dp[i] 1保证每个元素自己就能构成一个长度为1的子序列漏掉这一行结果就全错了。LIS还有一个 O(n log n) 的进阶做法用 d 数组维护长度为 len 的递增子序列的最小结尾元素配合二分查找。这个做法严格说属于贪心二分但理解它需要DP的状态概念能反过来加深你对“状态到底在记录什么”的认知。面试时如果能从 O(n^2) 自然过渡到 O(n log n)是很加分的。4.2 区间DP把“合并/分割”问题拆成区间区间DP的状态一般是 dp[l][r]表示处理连续区间 [l, r] 的最优结果转移靠枚举区间内的分割点。典型例子是石子合并一排石子堆每堆重量已知每次合并相邻两堆代价是两堆重量之和目标是最小总代价。先用前缀和数组 s 预处理合并任意区间 [l, r] 的代价即 s[r] - s[l-1]。然后转移方程写为dp[l][r] min(dp[l][k] dp[k1][r] s[r] - s[l-1])其中 k 从 l 到 r-1这个方程的意思很直白在分割点 k 处把 [l, r] 分成左右两堆分别合并好最后再把两堆合并一次。枚举所有可能的 k取最小代价。区间DP最关键的陷阱是循环顺序必须先枚举区间长度 len从2开始再枚举左端点 l然后计算右端点 r l len - 1。如果先枚举左端点再枚举右端点你会发现转移时依赖的短区间 dp[l][k] 或 dp[k1][r] 还没有被计算出来结果全是0或者初始值。我常用一个比方帮你记忆先算好所有短区间才能拼长区间所以“长度”一定要是最外层循环。矩阵链乘法是区间DP的另一个模板题结构和石子合并几乎一样只是合并代价从重量和变成矩阵乘法次数。会了石子合并这类题基本是换汤不换药。4.3 数位DP按位枚举时如何用状态记忆“卡界”数位DP解决的是“统计区间 [L, R] 内满足某条件的整数个数”的问题。区间范围可能到 10^18 甚至更大逐个枚举完全不可能必须按十进制位处理配合DP缓存。核心模板是记忆化搜索 dfs(pos, ...custom, tight, lead)pos当前从高到低枚举到第几位tight前面枚举过的位是否和上界 R 完全一致如果是当前位只能取 0 到 R 在当前位的数字否则可以取 0 到 9lead是否仍处于前导零阶段用于处理数字前面的0要不要计入条件的问题。以“统计 [1, N] 中各位数字之和是 k 的倍数的数的个数”为例搜索函数可以写成 dfs(pos, mod, tight)mod 是已枚举数字位之和模 k 的结果。边界条件是 pos 枚举完返回 1 当且仅当 mod 0。记忆化的键是 (pos, mod, tight)因为同样处于 (pos, mod) 时前面位数是否卡上界的场景对应方案数可能不同。核心代码框架大致是这样def dfs(pos, mod, tight): if pos len(digits): return 1 if mod 0 else 0 key (pos, mod, tight) if key in memo: return memo[key] limit digits[pos] if tight else 9 res 0 for d in range(limit 1): res dfs(pos 1, (mod d) % k, tight and d limit) memo[key] res return res这里必须提醒一个常见坑tight 和 lead 建议都放进记忆化键里。有些题解为了省空间只在 tightFalse 时保存记忆化结果这种优化本身没错但对初学者来说很容易写错。我自己的习惯是全放进键里牺牲一点缓存命中率换取逻辑绝对清晰。等真的在大数据上跑不过了再回来针对 tight 优化也不迟。顺带一提最近热搜里的“车辆动态规划问题”如果抽象成“在给定时间/路程约束下统计可行路线或最优成本”也属于“状态压缩多阶段决策”的框架只是状态里除了位置还要带时间或剩余电量本质思路和数位DP按位扩展是一致的。5. DP和贪心、分治的区别不要把时间花在错误的方法上5.1 贪心失效的例子零钱兑换为什么不能“每次拿最大的”很多DP题最容易和贪心混淆。零钱兑换是那个最经典的“当场打脸”案例。硬币面额为 [1, 5, 11]目标金额 15。如果按贪心思路“每次拿最大面额”先拿 11剩下 4只能补 4 个 1总硬币数是 5。但最优方案是 555只要 3 枚。贪心在局部每一步都取“当前看起来最大的面额”恰恰破坏了全局最优——因为它没有从全局权衡大面额硬币带来的“找零困难”。DP怎么处理dp[i] 表示凑出金额 i 需要的最少硬币数初始化 dp[0] 0其余为 float(inf) 表示不可达。转移时枚举最后一枚硬币面额 cdp[i] min(dp[i], dp[i - c] 1)其中 c 遍历所有硬币且 i c这个方程枚举了所有可能的“最后一枚硬币”所以不会漏掉全局最优。最终 dp[15] 3。这也解释了DP的另一个本质它天然是在枚举所有决策组合只不过通过缓存把重复计算消掉了——用空间换时间。我的实战判断是面对“求最优值”的问题先尝试证明贪心可行比如“每次拿最大面额在所有情况下都最优”证明不出来就果断切换到DP。面试时如果被问为什么不用贪心直接举反例比空口解释更有说服力。5.2 一张表看清什么时候能用DP什么时候该用贪心/分治经常有读者问我DP和分治到底什么关系和贪心什么区别我用下面这张表来概括希望能帮你建立一个全局坐标系方法核心特征子问题是否重叠适用提问方式典型例子贪心每步局部最优直接构成全局最优不关心求最值且能证明贪心选择性质活动选择、哈夫曼编码分治拆出的子问题相互独立合并结果不重叠适合递归分解无后效归并排序、快速排序动态规划缓存重复子问题组合子问题最优解必须重叠求最值、方案数、可行性0-1背包、LCS、零钱兑换回溯深度优先搜索所有可行解带剪枝允许一般不缓存枚举所有方案或路径八皇后、全排列这张表是我个人的分类不一定绝对严谨但对做题很有指导意义。分治和DP不是对立的DP本质上就是“分治 记忆化”先把大问题拆成小问题发现子问题重叠后用缓存兜住。所以我建议你拿到一道新题时先别急着套模板而是用分治的思维想这道题怎么拆每个子问题之间的依赖关系是什么画出依赖图之后DP的轮廓也就出来了。贪心和DP的分界同样清晰贪心一旦做出某个选择就不会再回头修改DP则把每个可能的选择都放进状态竞争最后用最优值说话。记住贪心不是DP的简化而是需要严格适用条件的独立算法。别为了一时省事去赌贪心很可能赌输。6. 调试DP的几个土办法和常见翻车点6.1 初始化翻车同一个dp[0]意义可能完全不同DP bug里初始化错误排在第一位。我举两个对比最明显的例子上台阶方案数dp[0] 表示“从第0级出发到达第0级的方案数”理解成空路径应该为1如果设成0那么 dp[2] 也会变0整道题就崩了。零钱兑换最小硬币数dp[0] 表示“凑出0元需要0枚硬币”为0没问题但 dp[1..amount] 要先初始化为无穷大表示不可达这样 min 操作才能发挥作用。这两道题的关键差异在于组合计数问题里“空集”也是一种方案所以 dp[0] 1最优化问题里“空集”通常不是合法方案或者代价是0所以 dp[0] 0 且其余初始化为无穷。所以我说初始化前先问“下标为0的状态在语义上是什么”而不是从上一道题的模板直接抄。我曾见过一位候选人背模板把上台阶题的 dp[0] 写成0理由是“网上很多代码都这么写”。其实网上代码往往把 dp[1] 作为初值dp[0] 只是辅助位。所以关键不是背初值而是理解语义。6.2 遍历方向翻车0-1背包为什么必须倒序第二个高频翻车点是一维数组的遍历方向。0-1背包的一维写法内层必须倒序我之前说过原因倒序保证计算 dp[j] 时dp[j-w[i]] 还是上一轮物品循环留下的旧值从而每件物品最多被选一次。而完全背包物品无限取的一维写法内层必须正序因为正序会让 dp[j-w[i]] 已经被本轮更新过正好把“重复取当前物品”的最优值继承下去。这两个结论很容易记混。我的记忆技巧是你问自己“我希望用到的 dp[j-w[i]] 是本轮的新状态还是上一轮的旧状态”0-1背包用旧状态所以从大到小完全背包用新状态所以从小到大。把问题问清楚方向就不会错。还有一个边界问题一维滚动数组里容量循环的下界是 w[i]小于 w[i] 的 j 放不下第 i 件物品保持原值即可所以代码里写的是 range(W, w[i]-1, -1)。很多报错就出在把这个下界写成0或者把 w[i] 搞错导致多算或少算。6.3 对拍写暴力解法去验证DP解是最高效的手段最后分享一个土办法却是我认为调试DP最高效的方法对拍。具体流程分三步对同一道题先写一个绝对正确的暴力解法通常是DFS枚举或朴素循环复杂度可以很高只要数据小能跑就行。再写你的DP解法。随机生成大量小规模测试数据分别跑两个解法比较输出。如果全部一致基本可以认为DP正确一旦不一致立刻得到一组能复现bug的测试用例。举个例子0-1背包的暴力解法可以这样写DFS枚举每件物品选或不选N10时毫无压力。DP解法就是标准模板。随后随机生成 N 在5到8之间、容量在10以内的多组数据做对拍基本能把所有隐藏边界都试出来。为什么这份工作如此有效因为DP bug往往藏在边界条件、初始化、循环方向这些需要“想”而不容易“看”出来的地方而暴力解法恰好直接给出正确答案。两者一对比问题定位的时间能从小时级缩短到分钟级。我现在写DP题速度再慢也会顺手写一个暴力版本做验证这个习惯帮我躲过了无数超时或Wrong Answer的尴尬。最后说一点个人体悟。很多人问DP水平怎么提升我的答案只有六个字多做题、多复盘。但复盘不是把错题本抄一遍而是每次做完题问自己状态为什么这么定义有没有更省维度的定义转移方程里的“动作”究竟是哪个如果把某个维度去掉会不会出错把这些问题想清楚比盲目刷一百道题有用得多。我自己的习惯是给DP题建一个分类索引线性DP、背包DP、区间DP、数位DP、状态压缩DP。拿到新题先归类再用对应的套路起步套不进去的往往是状态维度或转移动作没找对这时我就退回到“暴力递归→找重复子问题→加缓存”的原始推导路线而不是硬套模板。动态规划的题目永远做不完但建模能力是通用的值得你花时间彻底掌握。