区间DP算是我刷题时最后才克服的模型之一。刚接触动态规划那会儿背包、最长上升子序列这些“单点决策”的题目还好说一遇到石子合并、矩阵连乘、括号匹配这种需要像拼图一样把相邻区间拼起来的题就彻底懵了。后来我发现区间DP的本质并不复杂——把每个子区间当作独立问题把答案定义为区间上的一个函数再通过合并两个更小区间来推导当前区间。为了让你也能快速掌握这套思路这篇文章会从“线性DP为什么失效”讲起把状态设计、枚举顺序、经典变形题和常见边界错误一次讲透。无论你是刚开始学算法竞赛还是在准备面试算法题只要能把区间DP那套循环结构跑顺之后遇到各种变体都能很快抓住主线。1. 区间DP到底在解决什么从线性DP失效的边界说起1.1 线性DP为什么在这里会失效入门阶段我们常见的动态规划大多数属于“线性DP”。比如最长上升子序列dp[i]只和前面某个dp[j]有关背包问题中dp[i][w]只取决于dp[i-1][w]或dp[i-1][w-c]。它们的共同特征是每一步决策只影响当前位置状态之间是串行传递的前一个子问题解决后后面的子问题不会反过来推翻前面的结论。但有些问题一次操作会把整个区间的两端“粘”在一起或者在区间中间切一刀后两部分的答案会共同决定最终结果。这时如果还用一维线性状态会发现状态根本没法转移。拿括号匹配来说给你一串由()、[]组成的字符串问最少插入多少个字符才能变成合法括号序列。假设输入是([)]你尝试用dp[i]表示前 i 个字符需要补多少个括号走到第4个字符时发现前两个字符([如果能配对中间的两个字符[)会影响整体合法性这种“片段之间互相影响”的情况本质上是因为合法括号序列的判定具有递归嵌套结构它要求把一个区间整体压缩成一个字符再去和区间外配对。线性DP完全无法表示这种“区间整体塌缩”的过程。1.2 后效性如何通过“区间划分”消解区间DP的核心思路是把所有子区间[i, j]都看作独立的子问题先求出每个子区间自己的最优值然后再通过“合并两个相邻子区间”的方式推导更大的区间。这个过程之所以有效是因为它消解了后效性计算dp[i][j]时我们只需要用到长度严格小于j-i1的那些子区间的结果。这些子区间的值都已经在前面算好而且它们和区间外部的字符或数据没有任何依赖关系。就像一个大项目分成小组每个小组只负责自己的模块最后把所有模块按顺序组合起来不受其他小组进度干扰。你可以把区间DP想成“先算好所有小片段再逐步焊接成大片段”的过程。每一个片段都有自己的最终答案焊接时的规则是固定的因此整个推导链条是确定的。1.3 区间DP适用的数据特征并不是所有题目都适合区间DP我总结出三个特征满足它们时基本可以往区间DP上靠数据本身是连续序列比如数组、字符串、环状排列问题的最终答案可以由若干相邻子区间的最优答案合并得出合并代价通常与区间端点、区间总和或分割点有关且不随外部条件变化。例如“合并相邻元素得到最优解”“把一个序列划分成若干合法片段”“在区间上选择某个点把两边分别计算再组合”这些描述基本都指向区间DP。2. 标准套路拆解状态定义、转移方程与枚举顺序2.1 状态定义的第一性原则写区间DP第一步永远是定dp[i][j]的含义。不同的题目里它可以是合并[i, j]区间内所有元素的最小代价让[i, j]区间变成某种合法结构的最少操作次数[i, j]区间是否满足某个属性或者能构成多少个满足条件的子区间。定义状态时只有一个原则需要坚持[i, j]的答案必须能独立计算并且计算时只依赖比它更小的两个相邻子区间。如果发现你的状态定义还需要依赖区间外信息那就要重新调整。2.2 转移方程的通用骨架枚举分割点区间DP的转移几乎都长一个样。用伪码表示就是for len 2 to n: for i 0 to n - len: j i len - 1 dp[i][j] INF for k i to j - 1: dp[i][j] min(dp[i][j], merge(dp[i][k], dp[k1][j], cost(i,k,j)))这里的merge可以是取最小值、取最大值、累加方案数等等cost(i,k,j)表示把左边区间和右边区间合并成一个整体时额外产生的代价。为什么一定要枚举一个分割点 k 呢因为对于任意一个连续区间如果你把它“切开”不管怎么切它总能被分成左边一段和右边一段两个连续子区间。既然问题要求“区间内部的所有元素最终形成一个整体”那么最后一步操作一定发生在某个分割点上把左右两部分的答案合并起来。枚举 k 的实质就是在枚举“最后一步操作发生在哪里”。2.3 为什么必须按区间长度枚举两种可行写法对比不少新手会写成这样for i in range(n): for j in range(i 1, n): for k in range(i, j): dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost)这个问题初看似乎正常但实际运行时会错。原因在于你计算dp[i][j]时用到了dp[k1][j]这个子区间的右端点是j左端点却大于i。在循环顺序里当外层 i 固定、内层 j 递增时dp[k1][j]可能还没有被计算过。正确的写法是“按区间长度从小到大”枚举for length in range(2, n 1): for i in range(0, n - length 1): j i length - 1 for k in range(i, j): dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost)这样写保证了一个关键性质所有被引用的dp[i][k]和dp[k1][j]它们的区间长度都严格小于length因此一定已经在之前算好。换句话说长度循环本身就是拓扑排序它保证了依赖关系从短到长依次满足。有的代码里也会写成for i in range(n-1, -1, -1)加上for j in range(i1, n)的倒序写法。这种写法也能正确原因略有不同当外层 i 从大到小走时dp[k1][j]的左端点k1一定大于i而左端点更大的区间已经在外层更早的迭代中被计算过同时dp[i][k]的右端点更小而内层 j 是递增的所以它在更早的内层迭代中也被计算过了。但我个人建议还是用长度循环这也是最直观、最不容易出错的写法。倒序写法虽然简洁一旦状态定义复杂一点很容易把自己绕晕。2.4 初始化和三个基础小坑初始化一般分两类第一类是dp[i][i]的初始化表示长度为1的区间通常是0或者某个基础代价第二类是dp[i][i1]可能需要直接写死因为长度为2的区间有时会直接组成一个结果不依赖更小的区间。基础小坑有三个坑1k 的范围写错。k 的范围应该是i k j如果写成i k j那么当k j时会出现dp[j1][j]这是空区间很多语言的数组默认值会导致错误转移。坑2INF 取值过小。如果用dp数组存的初始值比较小两个大数相加时会产生错误答案一定要确保INF INF不会溢出C 里常用0x3f3f3f3fPython 里直接用float(inf)比较安全。坑3dp[i][i]没有正确处理。某些题目的区间长度为1时有特殊含义比如合并一堆石子本身不需要代价而矩阵链乘中单个矩阵也不需要乘法次数。这些必须根据题面挨个确认。3. 四道经典变形题同一个套路在不同外皮下的内核3.1 石子合并合并代价由区间总和决定石子合并是区间DP最经典的入门题。给出一排石子堆每次只能合并相邻两堆合并代价是两堆石子数之和求合并成一堆的最小总代价。状态定义dp[i][j]表示把第i堆到第j堆石子合并成一堆的最小代价。转移方程是dp[i][j] min(dp[i][k] dp[k1][j]) sum(i, j)这里的sum(i, j)为什么非要加在最后因为你无论怎么合并最后一次合并一定发生在某个 k 处左边变成一堆右边变成一堆最后这两堆合并时的代价就是两堆石子总重量之和而这个总重量恰好等于区间[i, j]的石子总数。所以转移的最后一定要加上区间总重量。对sum(i, j)的求法用前缀和数组是标准做法。前缀和可以 O(1) 得到任意区间的和否则区间DP的时间复杂度会从 O(n^3) 变成 O(n^4)数据量稍微大一点就跑不动了。这个题的进阶版是环形石子合并。如果石子排成环最朴素的想法是对每个起点都跑一次线性区间DP但更聪明的做法是把数组复制一份变成长度为2n的线性数组然后枚举长度为n的窗口取所有窗口结果的最小值。这个技巧我后面专门展开讲。3.2 矩阵链乘代价函数从“区间和”变成了“维度乘积”矩阵链乘问题是给定 n 个矩阵的维度序列用不同方式加括号总的标量乘法次数不同求最小乘法次数。假设第i个矩阵的维度是p[i-1] × p[i]区间[i, j]表示从第i个矩阵连乘到第j个矩阵。状态定义同样是dp[i][j]表示这组矩阵链的最小乘法次数转移方程为dp[i][j] min(dp[i][k] dp[k1][j] p[i-1] * p[k] * p[j])对比石子合并你会发现骨架完全一样只是代价函数从sum(i, j)换成了p[i-1] * p[k] * p[j]。很多初学者在这里疑惑为什么是p[i-1]而不是p[i]因为区间[i, j]连乘得到的结果矩阵维度是p[i-1] × p[j]。当你把[i, k]的结果和[k1, j]的结果做最后一次乘法时左边结果矩阵的维度是p[i-1] × p[k]右边结果矩阵的维度是p[k] × p[j]两个矩阵相乘需要的乘法次数就是三个维度相乘。所以这类题目最重要的地方不是背公式而是根据题面正确设计cost(i, k, j)。3.3 回文串分割当“答案”本身就在区间内部时给定一个字符串问最少切几次能把它切成若干回文子串。这类题的解题套路是先用区间DP预处理出所有子串是否为回文。这里有一个很巧妙的转移isPal[i][j] (s[i] s[j]) and (j - i 2 or isPal[i1][j-1])为什么j - i 2时可以直接为真因为长度为1、2、3的字符串只要首尾相等它一定是回文。长度再大时才需要检查去掉首尾后的子串是否回文。然后再用一次区间DP求最小切割次数dp[i][j] min(dp[i][k] dp[k1][j] 1)这题的“1”含义是在k和k1之间切一刀。如果你只想求整个字符串的最小切割数其实可以用一维 DP 优化到更低的复杂度因为切割线始终在端点之间移动。但如果题目要求任意子区间的最优切割数二维区间DP就是不可避免的。3.4 括号插入与多边形三角剖分状态转移的两种新姿势括号插入问题给定一个只含()、[]、{}的字符串求最少插入几个括号使其成为合法括号序列。这里的状态和转移比前几题更灵活。定义dp[i][j]为让[i, j]成为合法括号序列的最少插入数。转移分两种情况第一种如果s[i]和s[j]能配对我们可以尝试让它们作为最外层然后在区间内部继续修复即dp[i][j] min(dp[i][j], dp[i1][j-1])第二种无论能否配对都可以把区间分成两段分别修复dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j])注意即便两端能配对也仍然要枚举分割点。因为[i1, j-1]的内部不一定能修复成合法序列而把整个区间切成两段可能反而更优。这题的难点在于理解“配对”只是一个可选的转移分支而不是必须的选择。多边形三角剖分则是另一个思路凸 n 边形的顶点带权要求用不相交的对角线把它剖分成三角形使某种代价最小。状态定义为dp[i][j]表示顶点i到顶点j之间的子多边形的最小剖分代价转移时枚举第三个顶点kdp[i][j] min(dp[i][k] dp[k][j] cost(i,k,j))注意这里的子区间是[i,k]和[k,j]它们不是并排的区间而是共享了顶点k。这和前面几题的转移骨架略有不同你只要理解了“枚举最后一步操作的分界点”这个本质就能很快适应这种变化。4. 环形数组与下标边界一次完整的踩坑复盘4.1 断环成链为什么复制成两倍长度就能处理所有环形情况环形石子合并是经典的“断环成链”案例。石头排成一个环每次合并相邻两堆求最小代价。我第一次做这题时想的是枚举每一个起点分别跑一次线性DP后来发现代码写得很长还容易出错。标准解法其实很简单把数组复制一份得到一个长度为2n的数组然后枚举所有长度为n的窗口取各窗口计算结果的最小值。为什么这个做法是对的因为环上的任意一个“断开”位置总能在2n的线性数组中找到对应的连续长度为 n 的段。环的本来面目就是要从某个位置切断展开成链而长度为 n 的窗口恰好覆盖了所有可能的断口。看似是枚举了所有起点实际上只是利用了数组复制的技巧避免写重复的代码。代价是时间复杂度由 O(n^3) 升为 O((2n)^3)也就是常数项变为原来的8倍。对于 n 300 左右的数据完全没问题但如果 n 达到 1000 级别就需要考虑四边形不等式优化了。4.2 一个典型的错误实现从现象到根因下满这段代码是我某次训练时实际写出的错误版本现象是样例过不了最终答案总是偏小。# 错误示例 for length in range(1, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j 1): # 错误点 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i, k, j))表面上看循环枚举长度从 1 开始似乎没问题。但k的范围从i一直枚举到j当k j时它引用的是dp[j1][j]这是一个空区间。在 Python 数组里这个位置可能是上次计算留下的残留值如果残留值是 0那么整个转移就会错误地多出一条“合并一个空区间”的分支导致结果偏小。排查方法其实很简单把(i, j, k)的引用打印出来检查有没有出现dp[l][r]中l r的情况。另一个更快的方式是改成记忆化搜索递归天然不会产生空区间引用。如果你发现递推版答案和记忆化版答案不一致优先怀疑下标越界或空区间引用而不是逻辑本身。4.3 边界条件速查表为了让以后写代码时不至于每次重新踩一遍我把常见的边界问题整理成了表格位置常见错误正确做法区间长度起点length从 1 开始直接转移length1时只初始化转移从length2开始k 的枚举范围i k ji k jINF 的取值太小导致溢出或错误比较使用0x3f3f3f3f或float(inf)环形处理只枚举一个起点数组复制成 2n枚举长度为 n 的窗口前缀和下标使用 0-based 时边界混乱改用 1-based 前缀和统一sum(i,j)pref[j]-pref[i-1]记忆化状态忘记用memo判重先初始化memo[i][j] -1再递归这张表在我后来写网络流和树形DP时同样派上了用场很多边界错误根源其实都是“状态引用不合法”。5. 进阶优化与迁移思考从能写到会写5.1 记忆化搜索新手最不容易写错的形式区间DP除了循环递推还有另一种更符合直觉的写法——记忆化搜索。对所有不要求极限性能的场景我建议你刚开始训练时都先写递归版因为递归版天然按照“大区间调用小区间”的顺序执行不需要手动控制循环层级。def solve(i, j): if i j: return 0 if memo[i][j] ! -1: return memo[i][j] best float(inf) for k in range(i, j): best min(best, solve(i, k) solve(k 1, j) cost(i, k, j)) memo[i][j] best return best记忆化搜索的好处是可以剪枝、容易调试而且逻辑和公式一致。缺点是某些语言的递归深度有限但区间DP的数据范围通常只有几百到一两千一般不会爆栈。等理解了递归写法后再转成递推循环你会发现自己能更快地判断边界问题出在哪里。5.2 四边形不等式优化到底优化了什么区间DP的朴素复杂度是 O(n^3)。当 n 达到几千时即使递推写得很干净也可能超时。这时可以考虑四边形不等式优化。四边形不等式的核心条件是代价函数cost(i,j)满足四边形不等式以及单调性。满足条件时dp[i][j]的最优分割点k会随着区间变化而单调移动于是可以将枚举 k 的循环范围从[i, j-1]缩小在一个较小的区间内。判断到底能不能用最简单的办法是先写朴素 O(n^3) 代码跑几组小数据把最优 k 打印出来看是否单调。如果确实单调再实施优化。不要看到石子合并就无脑用四边形不等式因为很多变体的 cost 并不满足不等式条件强行优化反而会 WA。5.3 区间DP还能迁移到哪些场景区间DP的价值不只是那几个模板题我个人在字符串题里用到得不少。最长回文子序列就是很典型的区间DPdp[i][j] dp[i1][j-1] 2, if s[i] s[j] dp[i][j] max(dp[i1][j], dp[i][j-1]), otherwise还有一类题是“两个序列合并成一个求最小编辑代价”如果操作只能在相邻位置进行也往往会在区间上推。更远的迁移是树结构树的 DFS 序本身就是一个区间树上某些剖分问题等价于区间DP。比如“给一棵树加括号”“网络拓扑合并问题”本质上都是把一段连续区间不断合并成更小的问题。我在实际训练中形成了一套自己的做题顺序先确定是否满足区间DP三大特征再写出dp[i][j]含义然后写记忆化版本验证正确性最后换成递推并检查边界。这个流程让我从“看着石子合并答案都费劲”变成“看到区间合并就能快速建模”。如果你正在被区间DP卡住不妨也试试这个顺序先别急着背模板找一道题把记忆化版本写到 AC然后手动改成递推体会两种写法下状态依赖的不同。等你能流畅地说清楚“为什么长度循环可以保证子区间已经算完”这一关就算真正过了。
