区间DP从入门到进阶：状态设计、转移框架与经典模型详解

第一次正式接触区间类动态规划，是在刷一本通提高篇的时候。题目叫石子合并，当时看题解，代码只有二十行，但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[k+1][j] + w(i, j, k))

其中 k 是一个断点，取值范围一般是 [i, j-1]，opt 是 max 或 min，w(i, j, k) 是这一步合并/划分产生的额外费用。

直观理解一句话：要处理大区间 [i, j]，先把它从某个位置 k 切成左右两半，左半边 [i, k] 得到最优值，右半边 [k+1, j] 得到最优值，最后把这两半“拼起来”，代价是 w。至于这个 w 到底是什么，每个题不一样。

为什么要枚举所有 k？因为在最优方案里，最后一次切割/合并的位置我们事先不知道。把 i 到 j-1 每个位置都试一遍，总能试到那个最佳断点。这也是区间DP时间复杂度的来源：状态 O(n²) 个，每个状态转移 O(n)，总复杂度 O(n³)。

1.3 遍历顺序：先枚举长度，再枚举起点

这个点看起来小，但踩坑的人特别多。dp[i][j]依赖的是dp[i][k]和dp[k+1][j]，这两个区间的长度都严格小于j-i+1。如果你按 i 从1到n、j 从i到n 的顺序枚举，那么算dp[1][3]时dp[2][3]可能还没算过，用到的就是垃圾值。

正确顺序是：先枚举区间长度 len，从2到n；再枚举左端点 i，从1到n-len+1；右端点j = i+len-1。这样算任何区间时，它依赖的所有更短区间都已经算完了。初始化的dp[i][i]看作长度为1的区间，在 len=1 时处理。

提示：只要看到区间DP的代码，先检查三层循环是不是“外层长度、中层起点、内层断点”。顺序错了，小数据可能碰巧对，数据一多就全乱。

2. 两个必写的入门模型：石子合并与括号序列

2.1 石子合并：我把每一步都拆开讲

题目背景：N 堆石子排成一条线，每堆有一定重量，每次只能合并相邻两堆，合并代价是这两堆的重量之和，问全部合并成一堆的最小总代价。

状态定义：dp[i][j]表示把区间 [i, j] 的石子合并成一堆的最小代价。初始化dp[i][i] = 0，其他为 INF。

转移方程：

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i, j), i ≤ k < j

这里的sum(i, j)表示第 i 堆到第 j 堆的重量总和，用前缀和 O(1) 算。为什么每次转移都要加sum(i, j)？我用一个生活化的类比解释：不管前面怎么合，最后一次一定是把整段石子分成左右两大坨，然后合并这两大坨，这一次的开销就是左边总重量加右边总重量，恰好等于sum(i, j)。而左边那次合并、右边那次合并的代价，已经被dp[i][k]和dp[k+1][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[k+1][j]就成了dp[j+1][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[i+1][j-1] + 2)。

第二类：无论匹不配对，都可以枚举断点 k，把区间拆成两段：dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][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，判断依据是什么

我把这三道题摆在一起对照：

看得出：状态都是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][i+n-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-len+1，所以条件是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_MAX，dp[i][k] + dp[k+1][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[k+1][j]变成dp[j+1][j]，这是一个“右端点小于左端点”的不合法区间。有些实现里它会返回0，看起来好像没影响，但会让转移多枚举一个无意义的方案，甚至掩盖真正的边界问题；有些实现里它是未初始化的垃圾值，结果就完全错了。

我建议写转移时，脑子里自动检查两件事：左边的区间至少包含 i，右边的区间至少包含 j，所以 k 必须满足i ≤ k且k+1 ≤ j，合在一起就是i ≤ k < j。

5.3 环状答案窗口取错

之前说过，翻倍数组后答案要枚举 i，取min(dp[i][i+n-1])。有的同学翻倍了，循环也写对了，最后输出却写成dp[1][n]，这就等于只考虑了“在1号位置断开”的情况，环状题目白做了。

还有一个小细节：输出前确认 dp 数组开到了 2n 大小，如果开成 n 大小，访问dp[i+n]直接越界，本地跑可能看不出问题，评测机上一跑就是数组越界或者神秘错误。

5.4 调试技巧：先小数据，再打印DP表

区间DP的调试比线性DP麻烦，因为状态是二维的，出错了不好定位。我的习惯是：

先写死一个 n=4 的小数据，手算一遍标准答案，然后用程序输出中间 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[k+1][j]，逻辑和迭代版等价。数据小的时候，两版结果应该完全一致。对拍跑通，基本可以确定转移方程没问题，剩下的就是边界和细节。

6. 进阶：四边形不等式优化什么时候值得用

6.1 优化的直觉

石子合并这类问题，O(n³) 在 n ≤ 500 时很轻松，但 n 到 1000 以上就有点顶不住了。这时可以考虑四边形不等式优化，把复杂度降到接近 O(n²)。

它背后的原理，简单说就是“最优断点有单调性”：当转移的额外费用 w 满足四边形不等式和区间单调性时，dp[i][j]的最优断点s[i][j]会落在s[i][j-1]和s[i+1][j]之间，也就是满足：

s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]

这样枚举 k 的范围就不是 [i, j-1]，而是[s[i][j-1], s[i+1][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] = 0，s[i][i] = i。然后注意访问s[i+1][j]时，i+1可能等于 j，此时s[i+1][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这一章，基本就能建立起来。