很多人刷动态规划都会遇到同一个尴尬题目看了不少题解也抄了十几篇第二天碰到新题照样一脸懵。问题往往不在数学能力而是脑子里没有一套“模型库”。我这些年带新人刷算法最常用的办法就是把题目收敛成母题尤其动态规划这个章节真正值得反复啃的母题其实就那么十来道我把它们拆成一张可以随时调用的思维索引今天这份笔记就是把这件事讲透。先说清楚这套笔记适合谁。如果你是零基础想弄明白动态规划到底在干什么如果你已经刷过一些题但总在“状态转移方程推不出来”这个环节卡住甚至如果你只是需要一个能应对笔试面试的快速复习框架这篇笔记都接得住。文章里的核心关键词就四个动态规划、线性 dp、动态规划的模型原理、洛谷动态规划题单。前三个讲的都是思维方式最后一个是刷题落地的地方我们会把它们串成一条线。1. 动态规划解题的思维框架1.1 先有状态再有转移我见过大量新人一上来就盯着递推公式背背完之后做新题立刻失效。原因很简单公式是“转移”但它建立的根基是“状态”。动态规划的解题顺序应该是定义状态 → 研究转移 → 考虑边界。这个顺序一旦颠倒后面全乱。什么叫状态用大白话说就是你打算用什么信息来描述“我已经算到了哪一步”。比如爬楼梯状态是“走到第 i 级台阶一共有几种方法”最大子段和状态是“以第 i 个数字结尾的子段和最大是多少”。状态定义得越准确转移方程就越容易水到渠成。很多题卡住不是解法难而是状态定义得模模糊糊自然不知道下一步怎么递推。我自己的习惯动作是先把题目里所有可能参与决策的维度列出来。数组下标够不够不够就加一维。一个序列不够那就两个下标。选到哪个物品了当前重量是多少当前在哪个位置这些关键词就是状态的雏形。状态代表了“我在哪一步、手里握着什么信息”转移代表“怎么从前面的状态走到当前状态”。这跟打游戏存档是一个道理你总得先知道自己在哪个关卡才能讨论怎么往下走。1.2 三个核心性质与我的速记法教科书上会告诉你动态规划依赖三个性质最优子结构、重叠子问题、无后效性。这三句话背出来不难但怎么判断一道题能不能用 DP需要一套更有操作感的方法。我的经验是拆成三个问题来问大问题能不能由若干小问题拼出来如果可以说明有最优子结构。这些子问题是不是被反复计算如果是DP 才比暴力递归有价值。当前阶段一旦确定后续决策是否只跟当前阶段有关如果有关说明状态设计有问题。举个例子最短路径为什么能用 DP因为从 A 到 D 的最短路一定包含从某个中间点 B 到 D 的更短路径这是最优子结构不同路径可能经过同几个中间点这是重叠子问题当前站在哪个城市就足以决定后面怎么走不需要关心之前是怎么来的这是无后效性。我把这个判断过程压缩成一句顺口溜大问题拆小小问题重复当前状态定未来。做新题的时候先在草稿纸上把这三点写出来写不出来就老老实实换思路别硬套公式。1.3 它和贪心、暴力的边界动态规划经常被人拿来和贪心放一起比较。简单说贪心是“每一步用目前看起来最优的走法”DP 是“每一阶段把所有可能都存下来最后取优”。贪心不能回头DP 会保留多条候选路径所以很多贪心做不了的问题 DP 能做。举一个非常经典的例子找零钱。如果硬币面额是 1、5、11要凑 15 块钱贪心会先拿 11再拿四个 1一共 5 枚但最优方案其实是三个 5只需要 3 枚。为什么贪心失败因为先拿最大的那一步把后续的最优可能给堵死了。DP 不会犯这个错它会把“目标金额 j 最少需要几枚硬币”全部算出来转移的时候逐个尝试每种面额最后自然能找到最优解。这就是“决策有分支”和“决策只走一条”的本质区别。那它和暴力搜索又有什么区别暴力搜索是画出整棵递归树每个节点都算一遍DP 是建一张表把重复计算的节点结果存下来。同一个子问题只需要算一次复杂度从指数级降成了多项式级。这是动态规划能解决实际问题的底层原因。2. 10 道必刷母题的整体设计2.1 为什么要从母题切入“母题”的意思不是让你背题而是让你掌握一类模型的最小骨架。我常说动态规划就像积木母题就是那几块最基础的标准积木。你先把这几块积木玩得足够熟之后看到花里胡哨的组合题才不会慌。洛谷动态规划题单里上百道题看着吓人但如果你按模型去归类会发现大部分题目都跳不出我下面列的十种原型。与其被题海消耗精力不如先把母题吃透。一个简单判断标准能不能在 30 秒内写出某道母题的状态定义、转移方程和边界条件。写不出来说明你还没吃透。2.2 母题清单与模型映射我把 10 道母题按模型做了张对照表方便你随时回查。这 10 道不是随机选的它们基本覆盖了笔试和竞赛里最常出现的动态规划模型序号母题原型状态定义核心转移所属模型1爬楼梯dp[i]表示到第 i 级台阶的方法数dp[i] dp[i-1] dp[i-2]线性 dp2数字三角形dp[i][j]表示走到第 i 行第 j 列的最大路径和dp[i][j] max(左上正上) 当前值坐标 dp3最大子段和dp[i]表示以 i 结尾的最大连续子段和dp[i] max(a[i], dp[i-1] a[i])线性 dp4最长上升子序列dp[i]表示以 i 结尾的最长上升子序列长度dp[i] max(dp[j] 1)ji 且 a[j]a[i]线性 dp5最长公共子序列dp[i][j]表示前 i 个和前 j 个字符的 LCS 长度末尾字符相同则 1否则取 max二维序列 dp6编辑距离dp[i][j]表示把前 i 个字符变成前 j 个字符的最少操作插入、删除、替换三者取最小二维决策 dp70/1 背包dp[c]表示容量 c 能获得的最大价值选或不选当前物品背包 dp8完全背包dp[c]表示容量 c 能获得的最大价值当前物品可以重复选背包 dp9石子合并dp[l][r]表示合并区间 [l, r] 的最小代价枚举分割点 区间累加和区间 dp10离散调度问题dp[mask][u]表示已经走过 mask 集合、当前位于 u 的最小成本从上一个点 v 扩展到 u状态压缩 dp这 10 道题的难度有非常清晰的阶梯1 到 3 是入门重点培养“状态”意识4 到 6 是进阶开始接触多维状态7 到 9 是高频考点几乎每场笔试都会出现第 10 道是分水岭用它来检验你是否真正理解“状态压缩”和“集合转移”。把这十个模型想明白再回头看洛谷题单很多题目你甚至不用看题解就能猜到大概做法。2.3 把这些题刷通意味着什么很多人误以为刷完这 10 道题就完事了其实不是。母题的价值在于它留下了三种可迁移能力第一看到“求最大/最小/方案数”能快速判断是 DP 还是贪心第二能根据问题维度数确定状态是几维数组第三能根据转移特征判断是线性、背包、区间还是状态压缩。比如你在洛谷动态规划题单里碰到一道“矩阵取数”的题脑子里应该立刻浮现数字三角形的影子因为核心都是“按行走每步选左边或右边”。又比如碰到“整数拆分”它其实就是背包模型换了层皮把容量换成目标整数把物品换成可重复使用的拆分块。这些联想能力就是母题刷出来的。3. 七类母题的核心拆解3.1 线性 dp从爬楼梯到最大子段和爬楼梯的原始描述是一次可以上 1 级或者 2 级问上到第 n 级有多少种方式。状态定义就是dp[i]转移特别朴素dp[0] 1 dp[1] 1 dp[i] dp[i-1] dp[i-2]为什么不是dp[i] dp[i-1] 1很多初学者会问这个问题。答案是想到第 i 级最后一步如果跨 1 级那么前面走的是第 i-1 级的方案数最后一步如果跨 2 级前面走的是第 i-2 级的方案数。两个不同来源的方案要加起来这才是状态转移的含义。爬楼梯真正的价值是帮你建立“这一步从哪里来”的思维习惯。最大子段和则展示了一个非常有用的技巧状态里带上“必须包含当前位置”这个约束。如果只定义dp[i]为前 i 个元素的最大子段和你会发现转移很难写因为新元素可能接在某个子段后面也可能另起一个子段但前一种情况下你并不知道前一个子段的末尾在哪。改成“以 i 结尾的最大子段和”之后转移就一目了然dp[i] max(a[i], dp[i-1] a[i])a[i]表示从 i 重新开始dp[i-1] a[i]表示接上之前的连续段。最后答案是所有dp[i]的最大值而不是dp[n]。这个细节非常关键它告诉你状态设计里加一个结尾约束往往能消灭一堆难缠的边界讨论。最长上升子序列同样用了这个技巧所以它俩是同一个套路的两道变体。3.2 二维 dp数字三角形与网格路径的“同款”转移数字三角形的题目长这样一个金字塔状的数字矩阵从顶层出发每次可以向左下或右下走问路径上数字之和最大是多少。状态就定义成dp[i][j]表示从顶层走到第 i 行第 j 列的最大路径和。由于每个点只能来自左上或正上两个方向转移便是dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]这种题目上手极其快因为方向已经被题目固定了。真正值得记住的是一个反向思考如果题目允许上下左右四个方向DP 就不好用了因为状态之间会形成循环依赖。这时候要么换思路要么需要引入层次迭代。学数字三角形不是学这道题本身而是学会观察“转移方向是否已知”。网格路径计数也是同一类。题目问从左上角走到右下角只能向右和向下有多少种走法。状态定义就是dp[i][j]表示到达 (i, j) 的路径数转移就是dp[i][j] dp[i-1][j] dp[i][j-1]。只要方向明确、无环DP 就是解这种题的首选。我在写这类二维 dp 时有个习惯先在草稿纸上把转移的依赖图画出来检查有没有指向“未来”的箭头。如果某个状态的依赖来自尚未计算的位置说明状态顺序设计错了得调整循环顺序。3.3 序列 dpLIS、LCS、编辑距离的统一视角最长上升子序列和最长公共子序列看起来风马牛不相及但它们都属于“序列匹配结构”的 DP。先说 LIS状态是dp[i]表示以第 i 个元素结尾的最长上升子序列长度转移需要枚举它前面的所有元素dp[i] max(dp[j] 1) # j 从 1 到 i-1且 a[j] a[i]这是一个 O(n²) 的朴素写法适合理解。想优化成 O(n log n)可以用二分维护“最小结尾值”但要先吃透朴素版本别急着跳步。我遇到很多人上来就背二分优化结果一到笔试让写朴素版反而写不出来这就是基础不牢。LCS 则是双序列模型的代表。设两个字符串是 s1 和 s2定义dp[i][j]表示 s1 前 i 个字符、s2 前 j 个字符能形成的最长公共子序列长度。转移看最后两个字符if s1[i-1] s2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])注意这里下标有一个偏移字符串下标从 0 开始dp 下标从 1 开始比较方便所以比较时要写s1[i-1]而不是s1[i]。这个“错位”问题我在后面排查章节会专门讲它是二维 dp 最容易出错的位置之一。编辑距离把二维 dp 推向了一个新高度它不再只是匹配而是带三种操作的决策。定义dp[i][j]表示把 s1 前 i 个字符编辑成 s2 前 j 个字符的最少操作数转移就是插入、删除、替换三个动作各算一遍dp[i][j] min( dp[i-1][j] 1, # 删除 s1 的第 i 个字符 dp[i][j-1] 1, # 在 s1 中插入 s2 的第 j 个字符 dp[i-1][j-1] (s1[i-1] s2[j-1] ? 0 : 1) # 替换或不操作 )我特别喜欢拿编辑距离来当“二维 dp 期末考试”因为只要边界稍微处理不好整个表就全是错的。它的边界不是简单置 0而是dp[i][0] i、dp[0][j] j含义是把一个字符串删空或把空串插入成另一个字符串需要的步数。3.4 背包模型0/1 背包与完全背包背包是 DP 里最实用也最容易变形的一类。0/1 背包描述为有 n 个物品每个物品有重量 w[i] 和价值 v[i]背包容量为 W每个物品最多选一次求能带走的最大价值。状态定义只有一维也能写dp[c] max(dp[c], dp[c - w[i]] v[i])但更稳妥的理解方式是从二维开始dp[i][c]表示前 i 个物品在容量 c 下的最大价值然后滚动掉 i。真正值得关注的是遍历顺序这也是 0/1 背包和完全背包的唯一区别0/1 背包容量从大到小遍历for c in range(W, w[i]-1, -1)。完全背包容量从小到大遍历for c in range(w[i], W1)。为什么有这个区别因为 0/1 背包要求每个物品只用一个逆序能保证dp[c-w[i]]还是“上一个物品”计算出来的旧值不会被当前物品覆盖。完全背包允许重复选正序遍历让当前物品可以被反复叠加刚好满足无限取用的需求。这个差别如果只能记住一条那一定要记住顺序决定选择次数。实际做题中背包的变体极多求方案数、求具体方案、多重背包二进制拆分、分组背包、依赖背包。但万变不离其宗先把这两个基础版本吃透再研究变体会轻松很多。对于洛谷动态规划题单里的背包子题单我的建议是每道变体都试着把它还原成 0/1 背包或完全背包的骨架。3.5 区间 dp石子合并区间 dp 是很多人的第一个瓶颈因为它和线性思维完全不同。石子合并的题目大意一排石子每次只能合并相邻两堆花费为两堆石子数之和问把所有石子合并成一堆的最小总花费。状态不再是以某个下标结尾而是描述一个连续区间dp[l][r] min(dp[l][k] dp[k1][r] sum[l][r])k 从 l 到 r-1sum[l][r]是区间 [l, r] 的石子总数代表合并这一整段时额外付出的代价。这里的难点有两个一是状态数量是 O(n²)转移要枚举分割点总复杂度 O(n³)二是循环顺序必须按照“区间长度从小到大”来不能按左端点顺序来。因为计算dp[l][r]时你需要的子区间要更短如果只按 l 递增循环长区间的依赖可能还没算出来。我的记忆方法是先循环长度再循环左端点。写成伪代码是这样for length in range(2, n 1): for l in range(1, n - length 2): r l length - 1 dp[l][r] INF for k in range(l, r): dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r] sum[l][r])区间 dp 的场景远不止石子合并矩阵链乘、回文串分割、多边形剖分都长着同一副面孔。识别特征很简单题目让你在一个序列上做“合并、切分、消去”操作而每次操作的影响只作用于一个连续段就可以考虑区间 dp。3.6 状态压缩 dp调度与车辆路径问题的入门解法第 10 道母题我要多说两句因为它直接对应“车辆动态规划问题”的高频应用。现实中的物流调度、快递派送、多站点巡检经常遇上一个最基础的问题一辆车从场站出发需要依次服务若干个客户点服务完每个点后返回场站怎么走总路程最短。这个问题抽象出来就是旅行商问题TSP而 DP 解法恰好用到状态压缩。状态压缩的核心思想是用一个整数的二进制位表示“某个点是否已经访问过”。假设有 n 个客户点那么访问集合 mask 的二进制第 k 位为 1 就表示第 k 个点已经服务过。状态定义是dp[mask][u] # 已经访问过集合 mask当前停在点 u 的最小成本初始状态dp[1起点][起点] 0。转移就是枚举上一个位置 vv 已出现在 mask 内且 v ! u把 u 点补进集合dp[mask][u] min(dp[mask ^ (1 u)][v] g[v][u])g[v][u]是点 v 到点 u 的通行成本。最终答案是min(dp[全访问][u] g[u][起点])也就是最后从某个客户点返回场站。为什么说这是本科阶段最值得掌握的高级 DP因为它把“集合”这个抽象概念变成了数组下标思维跨度特别大。但也正因为如此它天然适合用来检验自己有没有真正理解状态的含义。车辆调度问题在真实业务里还会加上多车、时间窗、容量限制但再复杂的约束底层也脱离不开“当前处于什么状态、下一步还能扩展到哪里”这个 DP 骨架。做竞赛题时这类题在洛谷叫“状压 DP”刷题顺序一般放在区间 dp 之后。4. 代码实现环节的避坑清单4.1 初始化、边界、索引对齐状态定义想清楚只是成功了一半代码里一个边界写错整个 dp 表就从那一个位置开始连环崩。我最常看到的三个坑全跟初始化有关。第一个坑是无脑初始化为 0。求最小值的问题比如石子合并和编辑距离通常初始化为一个很大的数INFi否则取 min 的时候永远是 0。第二个坑是忽略了 dp[0] 或空串的含义。编辑距离需要dp[i][0]i、dp[0][j]j爬楼梯需要dp[0]和dp[1]都等于 1数字三角形可能需要在矩阵外边包一圈 0 来统一边界判断。第三个坑是下标偏移。前面说的 LCS 里s1[i-1]就是典型很多代码写成了s1[i]结果前几个字符总是对不上。我的建议是写完代码之后人工模拟一条最短的用例。比如 LCS 就手动把abc和ac的 dp 表画出来把表里的数字填一遍能用纸笔走通再上编译器就会很有底气。4.2 遍历顺序决定正确性动态规划的遍历顺序不是随便定的它必须满足一个条件计算当前状态时所有依赖的状态必须已经被计算过。这句话值得用粗线画出来。一维 dp 比较直观从 1 到 n 从左往右扫就行。二维坐标类 dp 一般按行从左到右、从上到下扫描因为依赖来自左上、正上、左方。区间 dp 必须按区间长度从小到大这个在前面已经强调过。背包问题则涉及顺序的另一个维度0/1 是逆序容量完全背包是正序容量。状压 dp 又不一样它通常从小到大枚举 mask保证mask ^ (1 u)一定小于 mask从而确保转移发生时目标状态已经算好。当你不确定遍历顺序对不对时用最笨的方法把状态转移画成箭头图检查每条箭头是不是都指向“下标更小”的方向。如果不是就考虑换循环顺序或者引入带层级的递推。4.3 滚动数组和记忆化的选择时机很多 DP 题空间上可以做优化最常用的就是滚动数组。比如爬楼梯只需要记住前两个值0/1 背包能把二维压成一维。但我不建议入门阶段一上来就写滚动数组因为优化之后的代码往往丢失了“前 i 个物品”这一层语义边界和顺序更难理解。先把朴素二维版本写对、跑通再谈优化这是一个比较稳的路线。那什么时候用记忆化搜索什么时候用递推我的判断标准是如果状态转移方向复杂或者拓扑关系不太好理清甚至递归深度可以接受记忆化搜索往往更好写、更好检查。竞赛圈有个共识只要递归深度不大想不出递推顺序就先用记忆化保住正确性再考虑改递推。比如区间 dp 和树形 dp很多人第一版就是用记忆化写的。反过来如果递归深度可能到 10 万级别就老老实实改递推。5. 把母题刷成题单学习闭环5.1 题单怎么配母题用洛谷动态规划题单、AcWing 算法课程、力扣动态规划标签这几个地方我都被问过“要不要全刷”。我个人的观点是题单是母题最好的验证场但不建议无脑刷成千上百道。正确姿势是先花三到五天把十道母题亲手实现一遍每道题都做到不看题解能独立写出并说明转移理由。然后去题单里找同类变体每遇到一道新题先在草稿纸上标记它属于哪类母题、状态有几维、转移方向是什么。如果三分钟内能定位到模型就直接写代码如果定位不到说明母题掌握得还不够回到对应小节重新梳理。这里分享一个我自己刷题单时的操作模板每道题留三行笔记。第一行写“模型属于哪类母题”第二行写“状态定义一句话”第三行写“这题和母题的核心差异”。这样刷完整个题单等于给自己做了一本动态规划错题集复习成本极低。5.2 一张复盘表很多人刷题只是对答案不复盘这是进步慢的根源。我每次教新人都会给一张复盘表要求做一道题填一行题目模型我用的状态我写的转移卡住位置与母题的关系下次改进线性 dpdp[i] 以 i 结尾状态转移没问题没想到要取全局 max最大子段和变体先画几个样例这张表的作用不是记录而是逼你把“卡住的位置”抽象出来。你会发现痛点往往集中在同一个地方要么状态定义少了“结尾”约束要么边界初始值设错要么遍历顺序不对。这些问题在十道母题里已经全部出现过重复犯错时回头看看母题效率比再刷十道新题都高。5.3 从母题走向进阶模型的路十道母题只是地基地基之上还有一片大森林概率 dp、期望 dp、树形 dp、数位 dp、斜率优化、四边形不等式优化。我的建议是按特征去学而不是按名字去学。看到“期望最大值”去研究期望 dp它的难点在于“期望的线性性质”和“倒推状态”看到“树上的父子依赖”去研究树形 dp尤其是树上背包看到“n 的范围只有 20 或 30 左右”果断猜状压 dp看到“转移方程带 max 且具有单调性”再考虑斜率优化。这些进阶模型并不孤立它们很多都能从母题里找到影子。比如树上背包本质上就是树形结构上的分组背包数位 dp只不过是把线性 dp 的“下标”换成了数字的每一位。6. 实操中的典型错误与排查6.1 常见错误模式刷了这么多题有些错误简直是全国统一模板。我把高频错误整理成一张速查表你写题前和提交失败后都可以对照看看错误现象大概率原因排查方向结果一直偏小最小值问题初始化为 0检查 dp 初始化是否用了 INF结果一直偏大最大值问题取错了起始位置检查 dp[0] 的语义数组越界下标偏移没处理好检查 s[i-1] 之类的写法0/1 背包结果变成了“可重复选取”容量遍历方向写反把容量循环改为逆序区间 dp 结果错乱循环顺序没有按长度改为先长度后左端点答案依赖了未计算状态状态顺序设计错误画依赖箭头图检查拓扑样例能过大数据 WA数据范围导致复杂度爆炸考虑滚动数组或更优转移每一行我都踩过。尤其是“样例能过大数据挂”基本就是复杂度或边界问题和思路对错关系不大。6.2 心态问题与排查思路动态规划的学习曲线比较陡我见过很多人刷到区间 dp 就放弃了觉得状态太多根本想不清楚。这里我想分享一个真实的心态调整方法不要把“想出解法”当成唯一目标把“能定位到模型”当成目标。定位到模型之后哪怕转移方程还要查资料也比完全摸不着头脑强。遇到长时间想不通的题我的排查顺序是固定的先检查状态定义是否把“必须包含当前位置”这类约束写进去再检查边界初始化是否符合题意的空状态然后检查转移方向是否明确也就是有没有环最后检查复杂度如果 O(n³) 超时再考虑优化。这个顺序倒过来用常常会发现问题远比你想象的小。最后再分享一个实战里特别管用的小技巧动态规划做多了以后你可以主动给每道母题写一个“一句话题解”。爬楼梯就是“当前步由前两步叠加而来”最大子段和就是“要么重新开始要么继承之前”。当你把十道母题都压缩成一句话之后做题时大脑里会自动浮现这句话的匹配对象这就是模型化思考真正形成的时候。动态规划从来不玄学它只是一套反复训练后可以内化的决策思路希望这份母题笔记能帮你把它从“背不下来”变成“想得清楚”。
