1. 区间DP的本质与适用场景动态规划里区间DP是让很多新手头疼的一类题目。说来也怪单看状态定义和转移方程区间DP往往比背包、线性DP还简单但一到自己动手写代码错误率却高得离谱。我见过不少学了几个月的人遇到环形石子合并还是卡在初始化上。先说说区间DP到底在解决什么问题。简单概括在给定的线性序列上通过枚举分割点将大区间问题拆成左右两个小区间问题最终合并出全局最优解。最典型的就是石子合并——一排石子每次只能合并相邻两堆每次合并的代价是两堆石子之和问最终合成一堆的最小总代价。这个问题的关键在于“相邻”两个字。因为只能合并相邻所以任意时刻操作涉及的石子必然构成一段连续的区间。这给了我们一个极强的结构所有子问题都可以用一段区间[l, r]来表示而大区间的答案一定是从它的两个子区间合并而来。这种“用连续区间定义状态”的DP就是区间DP。判断一道题是不是区间DP我有个简单实用的标准问题描述里出现“相邻”“连续”“每次操作一段”之类的词而且合并代价可以由区间状态直接推导。典型场景包括石子合并、多边形剖分字符串回文分割最少切割次数矩阵链乘括号化问题最长回文子序列的区间版博弈类DP中双方轮流取石子、且取走的是某一端再深入一点看区间DP之所以适合这类问题是因为它利用了区间之间的组合性质——大问题的最优解需要依赖内部某个切割位置两侧的小问题最优解。这个性质和分治法有异曲同工之处但区间DP强调记忆化所有子区间的结果只计算一次避免重复递归。2. 核心套路状态设计、转移方程与枚举顺序2.1 状态设计的三要素区间DP的状态几乎有一个固定套路三要素缺一不可状态表示dp[i][j]表示区间[i, j]上的某种最优值可以是最大值、最小值、方案数、胜负状态转移方程枚举分割点 k把 [i, j] 切成 [i, k] 和 [k1, j]用子区间答案合并出当前答案边界初始化长度最小的区间通常是长度为1或2的区间需要直接确定因为无法再切分以石子合并为例状态定义为dp[i][j]表示合并第 i 堆到第 j 堆石子的最小代价。转移方程是dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j)) 其中 i k j这里的sum(i, j)是第 i 堆到第 j 堆石子的总重量也就是当前这次合并的实际代价。这个sum可以提前用前缀和算出来这也是区间DP里最常见的预处理手段。你可能会问为什么要单独加一个sum(i, j)而不是写在初始化里因为不管 k 取哪个位置最终 [i, j] 整体合成一堆时必然有一步是把左右两堆合成最终那一堆这一步的代价就是全部石子的总重量。所以sum(i, j)是必加项不管前面的最优方案是什么。2.2 最容易被忽略的枚举顺序区间DP和普通DP最大的区别在于遍历顺序。普通DP往往按位置从左到右推进比如dp[i]依赖dp[i-1]但区间DP的dp[i][j]依赖的是比它更短的区间dp[i][k]和dp[k1][j]这两个区间的长度都小于j - i 1。所以正确做法是外层循环枚举区间长度 len内层循环枚举起点 i再手动算出终点 j i len - 1最后一层枚举分割点 k。代码骨架如下for (int len 2; len n; len) { // 区间长度从小到大 for (int i 1; i len - 1 n; i) { // 枚举起点 int j i len - 1; // 计算终点 dp[i][j] INF; // 初始化为正无穷 for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum(i, j)); } } }这个顺序有个精妙之处计算长度为 len 的区间时所有长度小于 len 的区间已经被算完了。因为dp[i][k]的长度是k - i 1 lendp[k1][j]的长度是j - k len所以子区间的答案一定已经存在于表中。我第一次写石子合并时犯过一个典型错误外层按起点 i 枚举内层按终点 j 枚举。结果计算dp[1][5]时dp[2][5]还没算出来哪怕转移方程写对了结果也是错的。事后总结区间DP的遍历顺序不是习惯问题而是正确性问题。长度从小到大是区间DP的“铁律”其他顺序基本都是错的。2.3 前缀和预处理区间DP转移时sum(i, j)如果每次用循环求复杂度直接多一个 n整体变成 O(n^4)对 n500 就已经很吃力了。正确做法是前缀和vectorint prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] stones[i]; } // sum(i, j) prefix[j] - prefix[i-1]这个预处理极其简单但极容易被新手忽略。你可能会想反正 n 不大直接循环求和也行我在实际刷题中发现n300 时普通写法可能勉强跑过但 n1000 时直接超时。而且前缀和还有一个额外好处代码更简洁不容易在嵌套循环里写错下标。3. 经典问题实战从石子合并到多边形剖分3.1 石子合并完整拆解先看最基础的线性石子合并注意很多人初学时直接上环形其实线性版本才是理解核心的关键。全流程如下读入 n 堆石子重量计算前缀和prefix初始化dp[i][i] 0一堆石子不需要合并代价为0枚举区间长度 len 从 2 到 n枚举起点 i计算终点 j枚举分割点 k更新dp[i][j]最终答案就是dp[1][n]完整实现C:#include bits/stdc.h using namespace std; const int INF 1e9; int main() { int n; cin n; vectorint stones(n 1); vectorint prefix(n 1, 0); for (int i 1; i n; i) { cin stones[i]; prefix[i] prefix[i - 1] stones[i]; } vectorvectorint dp(n 1, vectorint(n 1, 0)); for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { int cost dp[i][k] dp[k 1][j] prefix[j] - prefix[i - 1]; dp[i][j] min(dp[i][j], cost); } } } cout dp[1][n] endl; return 0; }这里有个我踩过的坑初始化dp[i][i] 0后长度大于1的区间初始化必须为 INF否则min操作时未计算的值可能被当成 0 参与比较导致所有答案都不更新最终输出 0。你可能觉得这是常识但我见过很多人栽在这包括我自己第一次手写的时候——因为全局数组默认是 0随手初始化全 0然后转移时 min 操作一直取到 0输出永远是 0还找不到原因。3.2 环形石子合并断环成链如果石子摆成一个环问题就变成“环形石子合并”。这时经典的套路是断环成链把数组复制一份变成长度为 2n 的线性数组然后在长度为 n 的滑动窗口里求最小代价。// 将石子数组复制一遍 vectorint stones(2 * n 1); for (int i 1; i n; i) { cin stones[i]; stones[i n] stones[i]; } // 前缀和长度也是 2n for (int i 1; i 2 * n; i) { prefix[i] prefix[i - 1] stones[i]; } // DP 在 2n 长度上跑 // 最终答案是 min(dp[i][in-1]) for i in 1..n为什么要复制因为环形结构里“从哪里断开”是未知的而复制一次数组后每个长度为 n 的连续区间都对应一种断开方式。最后取所有起点 i 里dp[i][in-1]的最小值即可。这个技巧不仅限于石子合并凡是环形序列上做区间DP几乎都可以这样处理。比如环形多边形剖分、环形字符串回文等问题我都推荐先尝试“断环成链”把一个环枚举问题转换成线性枚举问题然后再套区间DP框架。3.3 矩阵链乘换个壳子同一个骨架矩阵链乘问题括号化的题意是给定若干矩阵的维度求完全括号化后乘法次数最小值。它的状态定义是dp[i][j] 第 i 个矩阵乘到第 j 个矩阵的最小乘法次数。转移方程是dp[i][j] min(dp[i][k] dp[k1][j] dimensions[i-1] * dimensions[k] * dimensions[j])你仔细看这个方程和石子合并几乎是同一个结构枚举分割点 k左右两个子区间答案相加再加上当前合并的代价。区别只在最后的sum变成了矩阵乘法带来的额外代价。所以只要你吃透了石子合并矩阵链乘实际上就是换了个代价函数的石子合并。我经常给朋友的建议是区间DP这一类题不要一道一道地背而是抓住“枚举分割点 子区间合并代价”这个骨架然后做题时先搞清楚三个问题状态dp[i][j]表示什么合并时额外代价是什么石子重量和矩阵乘法次数还是字符串匹配的有效性初始化边界是什么这三个问题想清楚之后代码框架几乎不用改直接填空就行。3.4 多边形剖分的实战变式一个凸 n 边形的顶点带权值将其剖分成 n-2 个三角形求某种最优值比如三角形权值乘积之和最小。这类问题也是区间DP但状态维度和转移方式略不同dp[i][j]表示从顶点 i 到顶点 j按顺序形成的多边形剖分最优代价转移时枚举三角形顶点 k把多边形切成 [i, k] 和 [k, j] 两部分代价是dp[i][k] dp[k][j] 权(i)*权(k)*权(j)注意这里 k 的端点处理和石子合并略不同因为三角形由 (i, k, j) 三个点构成子区间是 [i, k] 和 [k, j]它们之间有一个公共顶点 k但没有重叠边。这种变式的意义在于区间DP的“分割点”不一定把区间分成左右两部分也可以按照几何结构切分。但本质上依然是“大区间依赖小区间”。所以核心思维不变变的只是转移方程的形态。刷题见多了你会发现其实很多看似新奇的区间DP题都是石子合并、矩阵链乘、多边形剖分这三板斧的排列组合。4. 进阶技巧四边形不等式与常见优化4.1 四边形不等式优化原理石子合并的朴素复杂度是 O(n^3)。n 到 400~500 时还好但到 1000 以上就可能卡时间。这时候你需要考虑优化。区间DP里最常见、也最实用的优化是四边形不等式优化。它的核心结论是如果转移满足四边形不等式和单调性那么最优分割点k的取值具有单调性——即dp[i][j]的最优分割点一定夹在dp[i][j-1]的最优分割点和dp[i1][j]的最优分割点之间。更直白的写法是opt[i][j] 表示 dp[i][j] 取最优值时 k 的选择 则 opt[i][j-1] opt[i][j] opt[i1][j]于是内层枚举 k 的范围可以缩小到区间[opt[i][j-1], opt[i1][j]]均摊复杂度从 O(n^3) 降到 O(n^2)。这个优化在很多题目里是“救命稻草”。石子合并的转移代价是prefix[j] - prefix[i-1]这个代价满足四边形不等式的条件前提是石子重量非负所以可以用这个优化。但要注意不是所有区间DP都能套四边形不等式。比如某些代价函数不满足决策单调性硬套反而会出错。我在实际做题中会先用朴素写法提交如果超时再考虑优化而不是一上来就套避免浪费精力在错误的优化方向上。四边形不等式优化的代码框架大概是for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; int k_start opt[i][j - 1]; int k_end opt[i 1][j]; for (int k k_start; k k_end; k) { int val dp[i][k] dp[k 1][j] prefix[j] - prefix[i - 1]; if (val dp[i][j]) { dp[i][j] val; opt[i][j] k; } } } }4.2 输出最优方案不只是算最小值很多时候题目不只是要最小值还要输出具体的合并顺序或分割方案。比如多边形剖分题经常要输出剖分线石子合并有时要输出合并过程。做法是开辟一个record[i][j]数组在转移更新时记录下最优的分割点 k。最后递归地从record构建方案void printScheme(int i, int j) { if (i j) { cout merge pile i \n; // 实际输出格式按题目要求 return; } int k record[i][j]; printScheme(i, k); printScheme(k 1, j); // 输出合并 i..j 的动作 }这一步非常容易漏很多人写出 DP 后发现题目要求输出方案只能临时改代码还得在转移方程里同时维护两个数组。我的经验是一开始就把 record 数组写上哪怕题目没要求因为调试的时候你也能通过它看到最优分割点到底是什么排查逻辑错误时极其有用。4.3 滚动数组在区间DP里踩坑背包问题里滚动数组能省空间。区间DP里很多新手也试图用一维滚动数组来省空间——这里我要明确提醒区间DP依赖的不只是“下一层”它依赖的是所有长度更小的区间不是简单的递推所以滚动数组很难应用。即使你强行压成一维也会因为子区间数据被覆盖而丢状态。唯一可能优化空间的情况是转移方程只依赖固定长度的子区间比如只依赖 len-1 的区间那是极少数特例。大部分区间DP老老实实用二维数组就好5000 x 5000的 int 矩阵大约 100MB很多题的 n 不会给那么大如果真的遇到 n 大到内存吃紧优先考虑四边形不等式顺便也能降低空间而不是滚动数组。5. 常见错误与调试技巧实录5.1 关于枚举顺序的三大常见错误我把训练中见过的区间DP错误整理成一个速查表每一条都是我实际踩过或帮别人排查过的错误类型表现根因解决方案外层按起点枚举答案不稳定或偏小计算大区间时依赖的右区间还没算好外层一律按区间长度枚举内层忘记限制ilen-1 n数组越界、结果诡异copy 代码时疏忽写循环条件时习惯性加上边界判断分割点 k 枚举到 n用到未定义状态对k j理解不透记住 k 最大取 j-1最小取 i第二类错误尤其隐蔽当 n 不够大时越界可能不报错读到了内存里的垃圾数据导致答案偶尔正常偶尔离谱。我排查这种问题最常用的方法是在小数据上手动模拟一遍把 n 设成 5 或 6打印所有 dp 值和手算结果对比。5.2 初始化陷阱汇总区间DP的初始化最容易踩的坑有这么几个dp[i][i] 忘记初始化为 0— 长度1的区间代价应该是0不初始化的话可能被当成 INF 或者某个奇怪值影响所有长度大于1的区间长度大于1的区间没有设为 INF— 因为全局变量默认是0min 操作可能选到0导致答案是0环形问题没复制数组直接在原数组上求 min(dp[1][n], dp[2][1])— 这种写法下标处理极其混乱容易出错第三点我在做环形石子合并时犯过好几次。最开始的思路是枚举断开点每次断开后跑一遍线性DP。虽然理论上可行但复杂度直接乘个 n而且每次都要重新初始化 DP 表实现麻烦还容易漏情况。后来老老实实用断环成链代码反而简洁了复杂度也从 O(n^4) 降到 O(n^3)。5.3 数据范围与复杂度速算经验区间DP的朴素复杂度是 O(n^3)所以n 100任意写法都能过放心用朴素框架n 500朴素写法通常能过但要注意常数优化比如把prefix的计算写成内联减少一次函数调用n 1000谨慎考虑四边形不等式优化或者检查是否有更小的状态设计有时可以缩成 O(n^2) 级别判断一道题能不能用区间DP我还有一个经验看 n 的大小。如果题目给的 n 小于 500基本上暗示 O(n^3) 是可以承受的如果 n 给了 5000 这种量级大概率有隐藏的贪心或者更高效的做法不一定是纯区间DP。5.4 我的调试三板斧每次写区间DP遇到 Bug我都会按固定顺序排查打印 dp 表把 DP 表以矩阵形式打印出来和手算的小数据对比。重点看 dp[1][2]、dp[2][3] 这些最小区间是否正确逐层往上核对。检查转移方程里的下标确认dp[i][k] dp[k1][j]里面的区间是否都在合法范围内。尤其注意 k1 是否超过了 j。检查代价函数石子合并里是前缀和差矩阵链乘里是三个维度的乘积。代价函数错一个下标结果就错得千奇百怪。这三种方法能解决我遇到的 95% 的区间DP Bug。剩下 5% 基本是四边形的单调性条件不满足、断环成链时数组没开够 2n 等边缘问题。6. 一套可以直接套用的模板最后分享一套我自己用着很顺手的区间DP模板基于石子合并框架兼容多种变形。我每次做区间DP都会从这套模板开始改省了大量重复思考的时间。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n 1); vectorint pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } // 定义 INF避免溢出通常取 1e9 或根据题目调整 const int INF 1e9; vectorvectorint dp(n 1, vectorint(n 1, 0)); // 注意dp[i][i] 此时已经是 0符合边界要求 for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { int cost dp[i][k] dp[k 1][j] (pre[j] - pre[i - 1]); if (cost dp[i][j]) { dp[i][j] cost; } } } } cout dp[1][n] \n; return 0; }用这套模板时你需要改的点只有三处代价函数pre[j] - pre[i-1]换成当前题的合并代价状态含义dp[i][j]根据题目改为 max、min、方案数等边界初始化如果长度1的区间不是0要及时调整套模板的心得有两条一先跑通再优化。不要一开始就加入四边形不等式、状态压缩等技巧。朴素版代码能过样例、能过小数据再去加优化。我见过太多人一次写优化版本Bug 混在一起根本调不出来。二模板里的 INF 根据数据类型调整。用 int 就 1e9用 long long 就 4e18。这个细节很多人不屑一顾但遇到更新时加一个很大代价的场景INF 设小了会被污染设大了加法溢出都会变成莫名其妙的答案。我对区间DP的体会是它不像背包那样有很多变体01、完全、多重、也不像树形DP那样需要复杂的DFS逻辑它更像一个固定的思维框架。你只要掌握了“小区间推大区间”的核心做题时先翻译问题成区间再套框架基本就稳了。这块内容后续还可以扩展的方向有两个一是三维区间DP比如括号序列里记录端点的状态二是区间DP与博弈论的结合双方轮流操作区间状态记录当前玩家的收益差。如果你已经能把石子合并和矩阵链乘写熟这些进阶题目其实也就是在现有骨架上加一个维度的事。最后分享一个小技巧练习区间DP时可以用纸笔手动推一个 n4 的例子把所有 dp 值算一遍再对照程序的输出。这个过程看起来慢却是我见过的最有效的理解方式。很多困惑——为什么枚举长度为什么初始化这些值——在手动推完一个完整例子之后都会豁然开朗。
