第一次正式接触区间类动态规划是在刷一本通提高篇的时候。题目叫石子合并当时看题解代码只有二十行但dp[i][j]这个东西我整整想了一晚上——为什么状态不是dp[i]和dp[j]两个一维数组非得开一张二维表后来我把数组一行行画在格子纸上才回过神来这类问题处理的是“一段连续区间”的最优决策大区间由两个相邻的小区间拼出来所以天生需要两个下标才能描述完整。这篇文章就把我从“对着模板抄”到“能自己判断一道题是不是区间DP”的完整过程写一遍。内容包括区间DP的状态设计与转移框架、两个最经典的模型石子合并、括号序列、环状问题的数组翻倍套路以及我踩过的几个隐蔽的坑。适合刚学完线性DP、准备啃一本通提高篇区间DP这一章的读者也适合学过一点但总写不对遍历顺序的人。1. 先把区间DP的底层逻辑捋清楚状态、转移、遍历顺序1.1 状态定义为什么必须是 dp[i][j]学过线性DP的同学都知道dp[i]一般表示“前 i 个东西的最优值”比如最长上升子序列、背包问题下标 i 就够了。可区间DP的问题里答案往往不只是“前 i 个”能描述的当你要合并一段石子、给一段括号序列配对、把一段区间划分成若干个三角形时决策的对象是一个 [i, j] 的连续区间起点和终点都会影响状态。举个例子石子合并里dp[i][j]表示“把第 i 堆到第 j 堆合并成一堆的最小代价”。为什么不能只用dp[i]因为你合并的是“从某一堆开始的一段”到底从哪开始、到哪结束这两个边界决定了这一段的总重量、也决定了一次次合并的切分方式。只记录终点起点信息就丢了。所以第一件事看到一道题如果它描述的是“对一段连续区间做某种操作”而且操作结果和区间两端都有关系就可以考虑用二维区间DP。状态定义通常写成“dp[i][j]表示区间 [i, j] 处理完的最优值”具体是最大还是最小、是代价还是长度看题面。1.2 转移方程的骨架枚举断点 k区间DP的转移百分之八十长这样dp[i][j] opt(dp[i][k] dp[k1][j] w(i, j, k))其中 k 是一个断点取值范围一般是 [i, j-1]opt 是 max 或 minw(i, j, k) 是这一步合并/划分产生的额外费用。直观理解一句话要处理大区间 [i, j]先把它从某个位置 k 切成左右两半左半边 [i, k] 得到最优值右半边 [k1, j] 得到最优值最后把这两半“拼起来”代价是 w。至于这个 w 到底是什么每个题不一样。为什么要枚举所有 k因为在最优方案里最后一次切割/合并的位置我们事先不知道。把 i 到 j-1 每个位置都试一遍总能试到那个最佳断点。这也是区间DP时间复杂度的来源状态 O(n²) 个每个状态转移 O(n)总复杂度 O(n³)。1.3 遍历顺序先枚举长度再枚举起点这个点看起来小但踩坑的人特别多。dp[i][j]依赖的是dp[i][k]和dp[k1][j]这两个区间的长度都严格小于j-i1。如果你按 i 从1到n、j 从i到n 的顺序枚举那么算dp[1][3]时dp[2][3]可能还没算过用到的就是垃圾值。正确顺序是先枚举区间长度 len从2到n再枚举左端点 i从1到n-len1右端点j ilen-1。这样算任何区间时它依赖的所有更短区间都已经算完了。初始化的dp[i][i]看作长度为1的区间在 len1 时处理。提示只要看到区间DP的代码先检查三层循环是不是“外层长度、中层起点、内层断点”。顺序错了小数据可能碰巧对数据一多就全乱。2. 两个必写的入门模型石子合并与括号序列2.1 石子合并我把每一步都拆开讲题目背景N 堆石子排成一条线每堆有一定重量每次只能合并相邻两堆合并代价是这两堆的重量之和问全部合并成一堆的最小总代价。状态定义dp[i][j]表示把区间 [i, j] 的石子合并成一堆的最小代价。初始化dp[i][i] 0其他为 INF。转移方程dp[i][j] min(dp[i][k] dp[k1][j]) sum(i, j), i ≤ k j这里的sum(i, j)表示第 i 堆到第 j 堆的重量总和用前缀和 O(1) 算。为什么每次转移都要加sum(i, j)我用一个生活化的类比解释不管前面怎么合最后一次一定是把整段石子分成左右两大坨然后合并这两大坨这一次的开销就是左边总重量加右边总重量恰好等于sum(i, j)。而左边那次合并、右边那次合并的代价已经被dp[i][k]和dp[k1][j]记过了。完整代码如下#include bits/stdc.h using namespace std; const int N 305; const int INF 0x3f3f3f3f; int n, a[N], sum[N]; int dp[N][N]; int main() { cin n; for (int i 1; i n; i) { cin a[i]; sum[i] sum[i - 1] a[i]; } memset(dp, 0x3f, sizeof(dp)); for (int i 1; i n; i) 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; for (int k i; k j; k) { int val dp[i][k] dp[k 1][j] (sum[j] - sum[i - 1]); if (val dp[i][j]) dp[i][j] val; } } } cout dp[1][n] endl; return 0; }说一下 k 的范围为什么要写成k j。因为当k j时右半区间是空的dp[k1][j]就成了dp[j1][j]没有任何意义。反过来 k 从 i 开始保证左半区间至少有一堆。边界处理是所有区间DP最容易写错的地方后面第5节我专门汇总。2.2 括号序列换个费用函数就换了个模型再看一道经典题给定一个由(、)、[、]组成的字符串求最长合法括号子序列的长度。比如()[]长度是4( [ ) ]这种虽然整体不对但子序列()或[]合法最长可能是2。状态dp[i][j]表示 s[i..j] 这个子串里最长合法括号子序列的长度。转移分两类第一类如果 s[i] 和 s[j] 配对那么它俩可以包住中间一段dp[i][j] max(dp[i][j], dp[i1][j-1] 2)。第二类无论匹不配对都可以枚举断点 k把区间拆成两段dp[i][j] max(dp[i][j], dp[i][k] dp[k1][j])。这个转移和石子合并的骨架完全一样但“合并代价”变了石子合并是强制加sum(i, j)括号序列则是可选的“2”和断点拆分。代码如下#include bits/stdc.h using namespace std; const int N 505; char s[N]; int dp[N][N]; int main() { cin (s 1); int n strlen(s 1); for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; if ((s[i] ( s[j] )) || (s[i] [ s[j] ])) { dp[i][j] max(dp[i][j], dp[i 1][j - 1] 2); } for (int k i; k j; k) { dp[i][j] max(dp[i][j], dp[i][k] dp[k 1][j]); } } } cout dp[1][n] endl; return 0; }注意这里dp[i][i]默认是0因为单个括号不可能组成合法序列。长度为1的区间不用初始化成 INF因为这道题里dp[i][i]就应该是0。2.3 模型对比都是区间DP判断依据是什么我把这三道题摆在一起对照题目状态含义额外代价 w常见方向石子合并链区间合并成一堆的最小代价sum(i, j)最小值括号序列区间内最长合法子序列长度括号配对时 2否则拆分最大值矩阵连乘区间矩阵链相乘的最小次数p[i-1] * p[k] * p[j]最小值看得出状态都是dp[i][j]转移都要枚举断点 k区别只在于“合并的规则”和“合并产生的额外代价”。所以做题时别被表面的描述迷惑只要满足“大区间由相邻小区间合并而来”这个特征优先往区间DP想。还有一个判断的土办法题目里如果出现“相邻两堆/两段合并”“把一段划分成若干段”“在区间内选择一个切分点”这类描述并且答案需要记住左右边界那大概率是区间DP。3. 环状区间DP数组翻倍法怎么处理最稳3.1 为什么环状会麻烦很多一本通的题会把链改成环比如环形石子合并N 堆石子摆成一个环每次合并相邻两堆问最小代价。乍一看和链状差不多但有个问题链状时我们有确定的两个端点“最后一次合并”一定是把整个 [1, n] 从某个断点分成两半那个断点在链里的位置是固定的。环状时任何一个位置都有可能是“最后合并的那一刀”的切分点换句话说环没有天然的起点和终点。如果你还是只算dp[1][n]那就只考虑了“在1号位置断开”这一种方案跨过 n 和 1 之间的合并会被完全漏掉。3.2 数组翻倍法把环拉成链枚举每一个断开位置标准做法是把原数组复制一份接在后面长度变成 2n。然后对 2n 长度跑链状区间DP最后答案不是dp[1][n]而是枚举起点 i 从1到n取min(dp[i][in-1])。为什么这样能覆盖所有情况因为任何一个环形合并方案都等价于“在环上某个位置切断然后按链合并”。我们枚举 i 从1到n相当于尝试了 n 个不同的切断位置每个位置对应一个长度为 n 的链求它的最优值再取最小。所有可能的“那一刀”都被试过了答案自然不漏。提示环状DP的复杂度是链状的 8 倍因为数组长度变成了 2n。n ≤ 200 时完全没问题n 到 1000 以上就要考虑四边形不等式优化也就是第6节要讲的内容。3.3 环状石子合并的完整实现#include bits/stdc.h using namespace std; const int N 405; const int INF 0x3f3f3f3f; int n, a[N], sum[N]; int dp[N][N]; int main() { cin n; for (int i 1; i n; i) { cin a[i]; a[i n] a[i]; // 数组翻倍 } for (int i 1; i 2 * n; i) { sum[i] sum[i - 1] a[i]; // 翻倍后的前缀和 } memset(dp, 0x3f, sizeof(dp)); for (int i 1; i 2 * n; i) dp[i][i] 0; for (int len 2; len n; len) { // 注意长度只到 n for (int i 1; i len - 1 2 * n; i) { int j i len - 1; for (int k i; k j; k) { int val dp[i][k] dp[k 1][j] (sum[j] - sum[i - 1]); if (val dp[i][j]) dp[i][j] val; } } } int ans INF; for (int i 1; i n; i) { ans min(ans, dp[i][i n - 1]); // 枚举起点窗口长度固定为 n } cout ans endl; return 0; }这段代码有三个细节容易被忽略第一外层 len 枚举到 n 而不是 2n因为我们只需要长度恰好为 n 的窗口更长的区间虽然也算出来了但对应的是环上加了超过一圈的合并不含答案第二起点范围要到2n-len1所以条件是i len - 1 2n第三最终答案必须用循环取 min不能直接输出dp[1][n]。能量项链那道题也很适合用同样的套路每颗珠子有头标号和尾标号相邻珠子共享一个标号合并产生的能量是三个数相乘。它本质上就是“环状矩阵连乘”代码骨架和上面几乎一样只是转移里的sum(j) - sum(i-1)换成了“合并时产生的能量”。4. 一本通提高篇的区间DP部分怎么刷最有效率4.1 这本教材的编排特点一本通提高篇在动态规划这块最突出的特点是例题少而精但每道题都是经典模型的一个变种。区间DP这一章我印象里从最基础的链状石子合并开始接着就上环状石子合并后面还有能量项链、多边形划分这类题目。它不会一次性把所有变形都堆给你而是让你从“会写模板”到“会改模板”。也正是因为这样刷这本教材时不要只看题解最好每道题都自己先抽象出两个东西状态dp[i][j]到底代表什么转移时的额外代价 w 是什么这两个想明白了代码只是体力活这两个想不明白抄十遍也记不住。4.2 建议的刷题顺序我自己带过几个学弟按下面这个顺序过这一章反馈都比较好第一步链状石子合并。要求不看题解能默写出完整代码并能解释为什么 k 的范围是 [i, j-1]。第二步环状石子合并。对比链状说出“数组翻倍 枚举起点取 min”的原因。第三步括号序列。感受“同样骨架不同费用”的区间DP训练自己从题面抽象出状态。第四步能量项链、多边形划分等变形题。重点是识别它们和石子合并、矩阵连乘的对应关系。第五步自己动手把链状石子合并改成“求最大代价”把数值改一改跑几组数据验证。每次做完一道题在代码最上方写一行注释记录状态定义和转移方程的口头表述。这个方法看起来笨但特别能暴露“我是不是真的理解了这个DP”。4.3 从会写模板到会判断题型很多人刷完这一章遇到新题还是懵原因在于只记住了石子合并的代码没有形成“这题是不是区间DP”的判断力。我自己的判断流程是三步先看题面有没有“区间/相邻/连续一段”的限制再试想如果只用dp[i]描述状态是不是会丢掉“右端点”这个关键信息最后看最优决策是否可以由两个更小的相邻区间组合而成。只要这三个答案都是肯定的就基本锁定了区间DP。举个例子有一类“把一段序列划分成若干块每块的代价是块内某种函数值求总代价最小”的题它看起来像线性DP但分隔点可能要枚举分隔代价又和左右边界相关这时候用区间DP写往往更自然。判断多了经验自然就来了。5. 藏得最深的坑初始化、断点范围和答案窗口5.1 初始化错误会让整个DP报废我踩过最蠢的坑是把dp[i][i]初始化为a[i]然后心安理得地跑合并。看起来“单堆石子重量是 a[i]”但dp[i][i]在状态定义里表示“这一堆已经合并成一堆”它本身就是一堆不再需要任何代价应该是0。如果写成a[i]每个长度为2的区间都凭空多算了一遍单堆重量答案直接偏移。另一个是 INF 初始化问题。写memset(dp, 0x3f, sizeof(dp))是竞赛里最常见的做法0x3f3f3f3f 大约是10亿多一点两个 INF 相加也不到 int 上限加 w 时仍然安全。如果你贪方便初始化成 INT_MAXdp[i][k] dp[k1][j]一加就溢出变成负数min 反而取到它答案直接归零。正确做法是dp[i][i] 0其余为 INF然后从长度2开始转移。5.2 断点枚举范围k j 是底线常见的错误写法是for (int k i; k j; k) { val dp[i][k] dp[k 1][j] w; }当k j时dp[k1][j]变成dp[j1][j]这是一个“右端点小于左端点”的不合法区间。有些实现里它会返回0看起来好像没影响但会让转移多枚举一个无意义的方案甚至掩盖真正的边界问题有些实现里它是未初始化的垃圾值结果就完全错了。我建议写转移时脑子里自动检查两件事左边的区间至少包含 i右边的区间至少包含 j所以 k 必须满足i ≤ k且k1 ≤ j合在一起就是i ≤ k j。5.3 环状答案窗口取错之前说过翻倍数组后答案要枚举 i取min(dp[i][in-1])。有的同学翻倍了循环也写对了最后输出却写成dp[1][n]这就等于只考虑了“在1号位置断开”的情况环状题目白做了。还有一个小细节输出前确认 dp 数组开到了 2n 大小如果开成 n 大小访问dp[in]直接越界本地跑可能看不出问题评测机上一跑就是数组越界或者神秘错误。5.4 调试技巧先小数据再打印DP表区间DP的调试比线性DP麻烦因为状态是二维的出错了不好定位。我的习惯是先写死一个 n4 的小数据手算一遍标准答案然后用程序输出中间 dp 表比对关键格子。打印可以在 len 循环结束后加一段for (int i 1; i n; i) { for (int j i; j n; j) { cout dp[i][j] ; } cout endl; }看对角线是不是符合预期看dp[1][n]附近的值是不是对得上手算结果。如果某个值异常偏大多半是初始化或者断点范围问题偏小多半是 INF 溢出了。再备一个暴力递归对拍。区间DP的递归记忆化其实很好写直接枚举 k 递归算dp[i][k]和dp[k1][j]逻辑和迭代版等价。数据小的时候两版结果应该完全一致。对拍跑通基本可以确定转移方程没问题剩下的就是边界和细节。6. 进阶四边形不等式优化什么时候值得用6.1 优化的直觉石子合并这类问题O(n³) 在 n ≤ 500 时很轻松但 n 到 1000 以上就有点顶不住了。这时可以考虑四边形不等式优化把复杂度降到接近 O(n²)。它背后的原理简单说就是“最优断点有单调性”当转移的额外费用 w 满足四边形不等式和区间单调性时dp[i][j]的最优断点s[i][j]会落在s[i][j-1]和s[i1][j]之间也就是满足s[i][j-1] ≤ s[i][j] ≤ s[i1][j]这样枚举 k 的范围就不是 [i, j-1]而是[s[i][j-1], s[i1][j]]每个状态转移的枚举量大幅减少。6.2 实现改动在石子合并的框架上加一个 s 数组记录最优断点for (int len 2; len n; len) { for (int i 1; i len - 1 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] (sum[j] - sum[i - 1]); if (val dp[i][j]) { dp[i][j] val; s[i][j] k; } } } }初始化时每个dp[i][i] 0s[i][i] i。然后注意访问s[i1][j]时i1可能等于 j此时s[i1][j] s[j][j] j是合法的。这个边界经常被忽略写的时候要留个心眼。6.3 新手要不要一上来就学优化我的建议是一本通提高篇前面那些例题数据范围都不大n³ 写法完全能过先把基础写稳更重要。四边形不等式优化的前提是 w 满足条件不是所有区间DP都能套盲目套反而会错。如果你刷完这一章还有余力可以单独找几道明确标注“可以用四边形不等式优化”的题练一练重点体会“什么时候能减少枚举范围”。对刚入门区间DP的同学来说能正确写出 n³ 版本、能处理环状、能判断题型已经达到这本教材的核心要求了。我个人还有一个小习惯每个区间DP题的dp[i][j]定义我会用一句话注释写在代码最上方比如“dp[i][j]区间[i,j]合并成一堆的最小费用”。这个习惯救过我很多次。因为当状态定义足够清晰时转移方程几乎是从定义里“长”出来的反过来一旦状态定义含糊写转移时就会反复犹豫 k 的范围和 w 的取值。最后再分享一个判断方法如果你看到一道题能自然地说出“dp[i][j]表示把第 i 到第 j 个东西处理完的最优值”并且转移时需要枚举中间点 k那十有八九就是区间DP。写熟几个经典题之后这类题的核心就不在循环怎么写而在对“合并规则”和“额外代价”的理解上。这个能力刷完一本通提高篇的区间DP这一章基本就能建立起来。