1. 内容整体设计与思路拆解1.1 为什么区间类动态规划值得单开一章先说个直白的判断区间类动态规划是信息学竞赛和算法面试里“性价比”特别高的一类题。它不像状压DP那样需要大量位运算技巧也不像数位DP那样对边界条件极度敏感但它对“状态划分”和“枚举顺序”的要求非常隐蔽。我见过不少选手背包问题、线性DP做得飞起一到区间DP就卡壳原因不是不会写转移方程而是没有建立起“小区间推大区间”的直觉。区间类动态规划的核心特征就一句话问题的解依赖于子区间的最优解。比如合并石子、矩阵连乘、括号配对、回文分割这些经典问题的共同点是大区间的最优解可以由两个或更多小区间的最优解组合而成。这个“组合”的过程就是枚举分割点或称为断点的过程。在一本通提高篇的教材体系里区间DP通常放在线性DP之后、树形DP之前这个位置安排是有讲究的。线性DP建立的是“从左到右”的递推思维区间DP则要求你跳出这个定式建立起“自底向上、由短到长”的区间扩展思维。而树形DP本质上又是区间DP的一种特化——树的中序遍历天然构成了一个区间结构树形DP的合并过程就是区间DP的区间合并过程。所以把区间DP吃透了后面学树形DP会轻松很多。1.2 区间DP的本质状态是一个“区间”普通DP的状态通常是一个整数 i代表“前 i 个元素”或“第 i 个位置”。区间DP的状态则是一个二元组 (i, j)代表“从第 i 个元素到第 j 个元素构成的闭区间”。这个转变看似微小实际影响巨大。一旦状态是区间你就必须考虑区间的长度、区间的枚举方向、分割点的选择范围等等。很多初学区间DP的同学最容易犯的错误就是按照线性DP的习惯外层循环枚举 i内层循环枚举 j结果发现转移时依赖的状态根本还没算出来。举个最经典的例子矩阵连乘问题。给定 n 个矩阵的维度序列求完全括号化方案的最小乘法次数。状态定义是 dp[i][j] 表示合并第 i 到第 j 个矩阵的最小代价转移方程为dp[i][j] min(dp[i][k] dp[k1][j] p[i-1] * p[k] * p[j]), i k j这个转移方程写出来很简单但如果你按 i 从 1 到 n、j 从 i1 到 n 的顺序去枚举计算 dp[1][n] 时你需要的 dp[1][k] 和 dp[k1][n] 可能都还没算出来。正确做法是先枚举区间长度 len再枚举区间起点 i然后计算终点 j i len - 1最后枚举分割点 k。这个“先长度、再起点、后断点”的三层循环框架就是区间DP的标准骨架。我在给一本通提高篇做配套练习时发现这个骨架的枚举顺序如果没讲透后面的回文串、石子合并、凸多边形划分等问题会全部踩在同一个坑里。所以这篇博客的第一个重点就是把状态定义和循环顺序讲清楚并且给出一个可以直接套用的模板。1.3 区间DP的适用场景与特征识别什么时候该往区间DP方向想我总结了三条识别特征基本可以覆盖大部分题目第一问题描述中出现了“连续子序列”、“子串”、“区间”这类关键词且操作对象是原序列的子区间。比如“每次选择一段区间进行操作”、“求将整个序列合并成一堆的最小代价”等这类表述天然指向区间DP。第二大问题的解可以分解为两个互不重叠的子问题的解的某种组合。注意“互不重叠”这个词很关键。线性DP的子问题通常表现为“前 i 个元素”和“前 i-1 个元素”这种包含关系而区间DP的子问题是“左半段”和“右半段”这种并列关系。第三操作顺序或合并过程具有阶段性和无后效性。区间DP要求你在处理一个区间时只关心该区间内部的最优值不关心该区间外部的任何信息。如果某个问题需要同时考虑多个区间的相互作用那就超出了标准区间DP的范畴。这三条特征需要放到具体题目里去体会。光讲抽象概念没用下面我会用一本通提高篇里出现频率最高的几类典型题目逐个拆解它们的思路和实现细节。2. 核心细节解析与实操要点2.1 区间DP的三种经典模型我把区间DP的典型题目归纳成三种模型。这三种模型的转移思路有共性但优化方式和边界处理各有侧重。搞懂这三种模型绝大多数区间DP题目都能对号入座。第一种是合并模型。典型代表是石子合并和矩阵连乘。这类问题的特征是把若干个元素按照某种规则合并成一堆每次合并有代价目标是代价最小或最大。转移方程原型是dp[i][j] min(dp[i][k] dp[k1][j] cost(i, j, k))其中 cost(i, j, k) 是合并左右两段时产生的额外代价。石子合并里这个 cost 是两堆石子的总重量之和矩阵连乘里这个 cost 是三个矩阵维度相乘的结果。第二种是分割模型。典型代表是凸多边形划分为三角形的最小代价、邮局选址问题区间版本。这类问题的特征是把一个大区间或大区域划分为若干子区域每个子区域单独结算目标是整体最优。转移方程形式和合并模型非常像但语义不同——合并模型是“合二为一”分割模型是“一分为二”。第三种是回文模型。典型代表是最少插入字符使其成为回文串、回文子串划分。这类问题的特征是对区间的两端进行操作状态转移往往同时压缩两端。比如 dp[i][j] 表示将子串 s[i..j] 变为回文串的最小操作次数转移时先看两端是否相等若相等直接由 dp[i1][j-1] 转移过来否则在两端做操作。这三种模型之间的关系不是割裂的。很多综合题会把合并模型和分割模型糅在一起或者在外面套一层线性DP。我见过一道题要求先做区间合并求每个小区间的得分再做线性DP统计总数这种嵌套结构在提高篇里不算罕见。2.2 枚举顺序与初始化的细节坑区间DP的三层循环很多人写了很多遍但每次都会在某些边界条件上翻车。我把这几个边界问题集中梳理一下。第一个坑是区间长度的枚举起点。长度为 1 的区间通常不需要转移直接初始化所以长度枚举通常从 2 开始。如果你从 1 开始也要确保 len 1 时的状态已经被赋值否则后面转移时会读到未初始化的垃圾值。第二个坑是分割点 k 的枚举范围。标准写法是 k 从 i 到 j-1或者 i1 到 j取决于转移方程怎么写但不同题目的有效范围可能不同。比如石子合并中如果要求每堆至少由两堆合并而来k 枚举到 j-1 保证左右两段都非空即可。如果题目允许空段那 k 的范围就要重新考虑。这个细节直接决定状态转移的正确性不能想当然。第三个坑是初始化值。求最小值时dp 数组要初始化为一个很大的数求最大值时初始化为 0 或很小的负数。这里很容易犯的一个错误是所有状态统一初始化为 INF 或 0导致某些非法状态被转移到了。正确做法是先用循环将所有 dp[i][i] 赋为 0长度为 1 的区间不需要合并再把所有 dp[i][j] (i j) 赋为 INF 或 -INF然后在转移时再更新。第四个坑是 dp[i][i] 是否需要特殊处理。有些题目中长度为 1 的区间代表一堆石头或一个矩阵它们的初始化值就是 0因为不需要做任何合并操作。但在另一些题目中比如回文分割长度为 1 的子串本身就是回文串dp[i][i] 应初始化为 1 或 0取决于 dp 数组的定义是“最少分割次数”还是“最少拼接次数”。2.3 四边形不等式与区间DP的优化切入区间DP的裸转移复杂度是 O(n³)n 在 300 左右问题不大但到了 1000 以上就明显吃力。这时候就需要引入四边形不等式优化或者说决策单调性优化。我不是在这里展开四边形不等式的严格数学证明那是论文级别的深度。实操中你只需要掌握判断条件如果 cost 函数满足四边形不等式并且决策点 k 的最优值随着区间右端点单调不减那就可以把第三层枚举的复杂度从 O(n) 降到均摊 O(1)整体从 O(n³) 降到 O(n²)。具体写法是记录 s[i][j] 表示区间 [i, j] 的最优分割点转移时枚举 k 的范围从原来的 [i, j-1] 收缩到 [s[i][j-1], s[i1][j]]。这个优化在很多石子合并变种题里能直接过掉大数据点收益非常大。但我要提醒一句四边形不等式优化不是万能药。它的适用前提是 cost 函数具有某种“单调性凸性”如果题目中的代价函数不符合这些性质强行应用会导致错误的答案。我见过一些同学在不明所以的情况下照抄优化模板结果样例都过不了排查半天才发现是优化条件不满足。提示判断能否用四边形不等式先做小规模暴力验证用裸 O(n³) 跑出正确答案后再套优化对比结果是否一致。这是最常见也最可靠的验证手段。3. 实操过程与核心环节实现3.1 石子合并从裸题到环状优化石子合并是区间DP的入门必做题一本通提高篇里也把它放在第一道例题。题目描述很简单有 n 堆石子排成一行每次选择相邻的两堆合并成一堆合并的代价是两堆石子的数量之和问将全部石子合并成一堆的最小总代价。状态定义 dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小代价。转移方程dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j])其中 sum[i][j] 是第 i 堆到第 j 堆的石子总数。这个 sum 可以通过前缀和 O(1) 计算这也是区间DP常用的预处理技巧。如果 n 不超过 300裸 O(n³) 就能解决。但如果石子排成一个环也就是第 n 堆和第 1 堆相邻问题就复杂了。标准做法是把数组复制一倍变成一条长度为 2n 的链然后跑 2n 规模的区间DP最后枚举长度为 n 的所有区间取最小值。这个链化技巧的本质是环上的任意一条长度为 n 的区间都可以视为“断开”后的线性结构把环转化为 n 条可能的链再在每条链上做线性区间DP。虽然总复杂度上升到 O(n³)但 n 在 1000 以内依然可行。我贴一份完整的 C 实现使用四边形不等式优化可以直接当作模板用#include bits/stdc.h using namespace std; const int MAXN 2005; const int INF 0x3f3f3f3f; int n, a[MAXN], pre[MAXN], dp[MAXN][MAXN], s[MAXN][MAXN]; int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i]); a[i n] a[i]; // 环状链化 } for (int i 1; i 2 * n; i) { pre[i] pre[i - 1] a[i]; } memset(dp, 0x3f, sizeof(dp)); for (int i 1; i 2 * n; i) { dp[i][i] 0; s[i][i] i; } for (int len 2; len n; len) { for (int i 1; i len - 1 2 * n; i) { int j i len - 1; // 四边形不等式优化缩小枚举范围 for (int k s[i][j - 1]; k s[i 1][j]; k) { int val dp[i][k] dp[k 1][j] pre[j] - pre[i - 1]; if (val dp[i][j]) { dp[i][j] val; s[i][j] k; } } } } int ans INF; for (int i 1; i n; i) { ans min(ans, dp[i][i n - 1]); } printf(%d\n, ans); return 0; }这段代码有几个值得注意的细节。第一dp 数组初始化为 INF 后再单独把 dp[i][i] 设为 0这样长度为 1 的区间不会被错误地参与合并。第二s 数组是决策点记录初始化为 i配合四边形不等式优化。第三最终答案遍历所有长度为 n 的区间取最小值因为环状结构下可能的最优断开点不止一个。3.2 括号配对与回文分割两端压缩型括号配对问题是另一种典型。给定一个由若干种括号组成的序列求最少添加多少个括号才能使整个序列成为一个合法的括号序列。状态定义 dp[i][j] 表示将子串 s[i..j] 变为合法括号序列的最少添加数。转移分两种情况。第一种如果 s[i] 和 s[j] 恰好是一对匹配的左右括号那么可以考虑让它们成对存在dp[i][j] 可以由 dp[i1][j-1] 转移而来。第二种无论如何都可以枚举分割点把区间拆成左右两部分分别处理dp[i][j] min(dp[i][k] dp[k1][j])。注意第二种转移是必定存在的因为它涵盖了一种情况s[i] 和 s[j] 并不匹配那么最优解一定存在某个分割点 k使得左半段和右半段分别处理。这个思维套路非常经典——“枚举断点分段处理”。回文分割问题则更进一步。给定一个字符串要求划分为若干子串使每个子串都是回文串求最少划分次数。这道题可以先用区间DP预处理出任意子串是否为回文串isPal[i][j] 表示 s[i..j] 是否为回文转移时看两端字符是否相同以及中间的区间是否为回文。完成预处理后再做一次线性DPdp[i] 表示前 i 个字符的最少划分次数转移时枚举最后一段回文串的起点 jdp[i] min(dp[j-1] 1)。这个“区间DP预处理 线性DP统计”的组合技巧在区间类问题里非常常见。它把二维的区间信息提炼成一个布尔矩阵或数值矩阵然后交给一维DP去组合使用。很多看似复杂的题目本质都是这种两段式结构。3.3 凸多边形划分与矩阵连乘代价计算细节凸多边形划分问题给定一个凸 n 边形的顶点权值将其通过不相交的对角线划分为 n-2 个三角形求所有三角形顶点权值乘积之和的最小值。状态定义 dp[i][j] 表示从第 i 个顶点到第 j 个顶点构成的子多边形的最优划分代价。注意这里的“从 i 到 j”指的是在凸多边形中按顺序排列的一段连续顶点。转移时枚举顶点 k 作为三角形 (i, k, j) 的第三个顶点然后递归划分左右两侧dp[i][j] min(dp[i][k] dp[k][j] w[i] * w[k] * w[j])看到这个方程你会发现它和矩阵连乘长得极其相似。没错矩阵连乘本身就是一种“线性链上的三角形划分优化问题”——我们把矩阵链划分成左右两部分然后计算划分点的乘积项。两个问题的数学结构完全相同只是实际背景不同。这里最容易踩的坑是下标偏移。矩阵连乘中n 个矩阵有 n1 个维度p[0] 到 p[n]dp[i][j] 表示合并第 i 个到第 j 个矩阵转移时用到的维度是 p[i-1]、p[k]、p[j]。很多同学写着写着就把下标搞混要么越界要么算出错误答案。我的建议是写转移方程之前先在纸上画出 n 个矩阵和 n1 个维度排成一行的图把下标对应关系标清楚再动手写代码。3.4 区间DP与记忆化搜索的取舍区间DP的循环写法是自底向上的递推但有些题目转移方程里会出现在同一个区间内部的递归调用比如最长回文子序列问题dp[i][j] dp[i1][j-1] 2 (s[i] s[j]) dp[i][j] max(dp[i1][j], dp[i][j-1]) (s[i] ! s[j])这种转移虽然也能用循环写但递归式的记忆化搜索写起来更直观不容易出错。而且当题目中区间的数量特别多、很多区间根本不会被访问到时记忆化搜索可以跳过无用状态实际运行可能比循环版本更快。我个人的体会是循环版本适合时间复杂度可预测、所有状态都需要计算的题目记忆化搜索适合状态稀疏、过程逻辑复杂的题目。在竞赛时间紧张的情况下选自己最熟练、最不容易写错的方式更重要不要为了“好看”去强行走某个固定模板。注意记忆化搜索时如果状态依赖的是“更大的区间”而非“更小的区间”循环版本可能根本无从下手但记忆化搜索天然支持任意方向的依赖。这也是它的一大优势。4. 常见问题与排查技巧实录4.1 为什么会陷入死循环或无限递归区间DP使用记忆化搜索时最常见的问题是依赖关系形成环导致函数反复调用自己。判断依赖方向的基本原则是区间长度必须严格递减。换句话说dp[i][j] 只能依赖长度小于自身的状态比如 dp[i1][j]、dp[i][j-1]、dp[i1][j-1]或者 dp[i][k] dp[k1][j]其中 k 在 i 和 j 之间左右两段长度都小于原区间。如果你发现自己写的递归函数始终没有走到递归边界检查一下是否有某个转移直接把 dp[i][j] 交给 dp[i][j] 自己处理了。这种错误在回文类问题中特别容易出现比如写回文判断的递归时忘记处理 i j 的边界情况导致无限递归。4.2 初始化顺序错误导致的“幽灵答案”区间DP的循环版本中状态的计算顺序完全由循环嵌套决定。如果你先枚举起点 i再枚举终点 j那么计算 dp[i][j] 时依赖的 dp[i1][j] 还没算出来因为外层 i 循环还没推进到 i1。结果就是答案要么是 INF要么是 0看起来极端不合理。排查方法很简单在 dp[i][j] 更新处的下一行打印 i、j、k 和当前 dp 值跑一个小样例观察状态是否按照“长度从小到大”的顺序被填充。如果有状态的长度顺序倒挂说明循环顺序写错了。4.3 字符串下标与数组下标混淆处理字符串相关的区间DP时常见的字符串索引是 0-based从 0 开始而数组循环习惯可能是 1-based从 1 开始。一旦混用会出现各种离奇的越界和错误。我的习惯是统一使用 1-based。读入字符串后在前面拼一个空格字符s s这样 s[i] 对应第 i 个字符前缀和、区间判断等操作都可以直接套用 1-based 循环不容易出错。这个技巧虽然看起来很小但在实战中能省下大量调试时间。字符串题目和数组题目共用同一套区间DP循环模板的需求非常普遍提前统一好下标体系是一劳永逸的做法。4.4 边界条件速查表我把区间DP常见题型的边界条件整理成一个速查表写代码时可以对照检查题型初始化转移注意点最终答案取法石子合并dp[i][i]0前缀和计算合并代价环状时取区间长度 n 的最小值矩阵连乘dp[i][i]0维度下标 p[i-1]*p[k]*p[j]dp[1][n]括号配对dp[i][i]1两端匹配时多一条转移路径dp[1][n]回文分割先预处理回文矩阵线性DP叠加dp[n]凸多边形划分dp[i][i1]0顶点编号循环取模枚举断点取最小值这张表不能覆盖所有变体但能帮你建立从题干到状态定式的对照感。做题时先把题干特征和表中模型对齐再决定状态定义和初始化方式能少走很多弯路。4.5 实战中必备的三个调试小技巧第一个技巧是写一个暴力对拍程序。区间DP题目复杂一旦答案错误很难直接定位是状态定义问题还是转移方程问题。我通常另写一个 DFS 枚举所有分割方案的暴力版然后和区间DP版本对拍随机小数据。只要两组结果在小数据上一致再去提交大数据就放心很多。第二个技巧是使用打印观察决策点。在 dp 数组更新时把使得 dp[i][j] 取得最优值的 k 记录下来也就是 s[i][j]。排查时打印 s 数组看看决策点是否符合直觉。比如石子合并里决策点通常集中在区间的中部如果出现极左或极右的异常决策多半是前缀和计算错了。第三个技巧是注意数据范围推理复杂度。看到 n ≤ 500基本可以确定要用 O(n³) 或更优的解法n ≤ 1000就要考虑四边形不等式优化n ≤ 5000标准区间DP基本不可能通过需要考虑别的思路可能不是区间DP或者需要更高级的优化。很多时候时间复杂度分析能帮你提前排除错误方向。5. 从区间DP到更高级DP的延伸5.1 区间DP与状态压缩DP的交织区间DP解决的是连续区间的状态设计问题状态压缩DP解决的是集合的状态设计问题。两者并非互斥很多题目会把它们结合起来用比如“给定一个圆环每次可以选择一段连续的弧进行染色问最少操作次数”。这类题目中区间长度和选择顺序都不是提前给定的往往需要先枚举一次操作的范围再递归处理剩余部分这本质上是一种区间上的搜索而每次选择的状态可以用位运算表示。处理这类混合题时关键是分清主次哪个维度是区间维度哪个维度是集合维度。通常区间维度负责描述操作对象的形状集合维度负责描述已经被处理过的部分。将二者分离后再用记忆化搜索去实现逻辑会比强行写成多重循环清晰得多。5.2 区间DP与树形DP的同构性前面提到区间DP和树形DP在结构上有天然的联系。树的中序遍历序列是树结构的一个线性表示而树形DP的合并步骤本质上就是在中序遍历序列上切分左右子树。一个典型的对应关系是树形背包问题给定一棵有根树每个节点有价值和体积选择一个包含根的连通块使总体积不超过限制的同时总价值最大。这个问题可以转化到树的 DFS 序上做区间DP——每个节点对应一个区间区间包含该节点的所有后代节点。在这个区间上做划分等价于在树上做孩子与子树的选择。这个转化的价值在于树形结构上的操作往往受限于父子关系的约束而区间DP的约束是“连续性”。一旦把树的 DFS 序映射到区间上原本复杂的依赖关系就变成了区间包含关系很多原来看起来无处下手的题目瞬间就有了清晰的解题路径。5.3 区间DP在真实业务场景中的应用很多人觉得区间DP只是竞赛题和实际工程没关系。这个印象不完全准确。虽然日常业务开发中不会直接写状态转移方程但理解区间DP的思维方式对解决某些实际问题很有帮助。举几个贴近工程的例子。字符串编辑距离相关功能中要计算两个字符串的相似度可以用最长公共子序列的思路而最长回文子序列的区间DP解法可以直接迁移到文本相似度判断上。数据压缩中有损压缩里的预测编码和区间划分问题也体现了“大区间拆小区间小区间合并大区间”的思想。具体到代码实现层面凡是涉及“区间上的最优切分”问题比如日志分段、批量任务调度、缓存分区策略等都可以用区间DP的思想建立模型再根据实际数据规模选择合适的实现方式。虽然 n 通常不会大到需要四边形不等式优化但状态设计和滚动数组优化的思路完全通用。所以我的建议是不要只把区间DP当成应试内容试着把它理解成一种通用的“区间问题思考框架”。做题是为了建立框架而框架一旦建立迁移到实际问题里会产生意想不到的作用。个人体会我从第一次接触区间DP到现在踩过的坑比大多数人要多那么一两个。最深刻的教训是不要为了追求优化而跳过暴力验证。多次做题时我直接套四边形不等式优化代码写得很漂亮但样例跑出来就是不对最后怀疑人生。退一步写个 O(n³) 暴力版对拍半小时内定位到问题才发现是 cost 函数根本不满足优化的前提条件。所以现在我的习惯是拿到一道区间DP题第一版永远是最朴素的三层循环先确保思路正确再根据数据范围考虑优化。裸的 O(n³) 能过就直接交过不了再上四边形不等式或其他优化手段。这个“先正确后优化”的顺序帮我省掉了大量无意义的调试时间。另外区间DP的状态设计虽然灵活但核心还是“找到划分点和合并代价”。很多时候想不出转移方程不是因为你不会DP而是因为你没有把题目中的“合并动作”或者“划分动作”抽象出来。试着用日常语言把过程描述一遍——比如“我要把这段区间分成两半左右各自最好地处理完然后拼接起来”——再把这个描述翻译成转移方程往往就通了。希望这篇长文能帮你把区间类动态规划这个板块啃下来。它不复杂但需要你动手写、动手画、动手对拍把直觉建立起来之后再遇到这类题就会发现它们其实长得都差不多。