企业官网建设流程全解析

区间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-i+1的那些子区间的结果。这些子区间的值都已经在前面算好，而且它们和区间外部的字符或数据没有任何依赖关系。就像一个大项目分成小组，每个小组只负责自己的模块，最后把所有模块按顺序组合起来，不受其他小组进度干扰。

你可以把区间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[k+1][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[k+1][j] + cost)

这个问题初看似乎正常，但实际运行时会错。原因在于：你计算dp[i][j]时用到了dp[k+1][j]，这个子区间的右端点是j，左端点却大于i。在循环顺序里，当外层 i 固定、内层 j 递增时，dp[k+1][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[k+1][j] + cost)

这样写保证了一个关键性质：所有被引用的dp[i][k]和dp[k+1][j]，它们的区间长度都严格小于length，因此一定已经在之前算好。换句话说，长度循环本身就是拓扑排序，它保证了依赖关系从短到长依次满足。

有的代码里也会写成for i in range(n-1, -1, -1)加上for j in range(i+1, n)的倒序写法。这种写法也能正确，原因略有不同：当外层 i 从大到小走时，dp[k+1][j]的左端点k+1一定大于i，而左端点更大的区间已经在外层更早的迭代中被计算过；同时dp[i][k]的右端点更小，而内层 j 是递增的，所以它在更早的内层迭代中也被计算过了。

但我个人建议还是用长度循环，这也是最直观、最不容易出错的写法。倒序写法虽然简洁，一旦状态定义复杂一点，很容易把自己绕晕。

2.4 初始化和三个基础小坑

初始化一般分两类：第一类是dp[i][i]的初始化，表示长度为1的区间，通常是0或者某个基础代价；第二类是dp[i][i+1]可能需要直接写死，因为长度为2的区间有时会直接组成一个结果，不依赖更小的区间。

基础小坑有三个：

• 坑1：k 的范围写错。k 的范围应该是i <= k < j，如果写成i <= k <= j，那么当k = j时会出现dp[j+1][j]，这是空区间，很多语言的数组默认值会导致错误转移。
• 坑2：INF 取值过小。如果用dp数组存的初始值比较小，两个大数相加时会产生错误答案，一定要确保INF + INF不会溢出，C++ 里常用0x3f3f3f3f，Python 里直接用float('inf')比较安全。
• 坑3：dp[i][i]没有正确处理。某些题目的区间长度为1时有特殊含义，比如合并一堆石子本身不需要代价，而矩阵链乘中单个矩阵也不需要乘法次数。这些必须根据题面挨个确认。

3. 四道经典变形题：同一个套路在不同外皮下的内核

3.1 石子合并：合并代价由区间总和决定

石子合并是区间DP最经典的入门题。给出一排石子堆，每次只能合并相邻两堆，合并代价是两堆石子数之和，求合并成一堆的最小总代价。

状态定义：dp[i][j]表示把第i堆到第j堆石子合并成一堆的最小代价。转移方程是：

dp[i][j] = min(dp[i][k] + dp[k+1][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[k+1][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]的结果和[k+1, 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[i+1][j-1])

为什么j - i <= 2时可以直接为真？因为长度为1、2、3的字符串，只要首尾相等，它一定是回文。长度再大时，才需要检查去掉首尾后的子串是否回文。

然后再用一次区间DP求最小切割次数：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + 1)

这题的“+1”含义是在k和k+1之间切一刀。如果你只想求整个字符串的最小切割数，其实可以用一维 DP 优化到更低的复杂度，因为切割线始终在端点之间移动。但如果题目要求任意子区间的最优切割数，二维区间DP就是不可避免的。

3.4 括号插入与多边形三角剖分：状态转移的两种新姿势

括号插入问题：给定一个只含()、[]、{}的字符串，求最少插入几个括号使其成为合法括号序列。

这里的状态和转移比前几题更灵活。定义dp[i][j]为让[i, j]成为合法括号序列的最少插入数。转移分两种情况：

第一种，如果s[i]和s[j]能配对，我们可以尝试让它们作为最外层，然后在区间内部继续修复，即：

dp[i][j] = min(dp[i][j], dp[i+1][j-1])

第二种，无论能否配对，都可以把区间分成两段分别修复：

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

注意，即便两端能配对，也仍然要枚举分割点。因为[i+1, j-1]的内部不一定能修复成合法序列，而把整个区间切成两段可能反而更优。这题的难点在于理解“配对”只是一个可选的转移分支，而不是必须的选择。

多边形三角剖分则是另一个思路：凸 n 边形的顶点带权，要求用不相交的对角线把它剖分成三角形，使某种代价最小。状态定义为dp[i][j]表示顶点i到顶点j之间的子多边形的最小剖分代价，转移时枚举第三个顶点k：

dp[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[k+1][j] + cost(i, k, j))

表面上看，循环枚举长度从 1 开始，似乎没问题。但k的范围从i一直枚举到j，当k = j时，它引用的是dp[j+1][j]，这是一个空区间。在 Python 数组里，这个位置可能是上次计算留下的残留值，如果残留值是 0，那么整个转移就会错误地多出一条“合并一个空区间”的分支，导致结果偏小。

排查方法其实很简单：把(i, j, k)的引用打印出来，检查有没有出现dp[l][r]中l > r的情况。另一个更快的方式是改成记忆化搜索，递归天然不会产生空区间引用。如果你发现递推版答案和记忆化版答案不一致，优先怀疑下标越界或空区间引用，而不是逻辑本身。

4.3 边界条件速查表

为了让以后写代码时不至于每次重新踩一遍，我把常见的边界问题整理成了表格：

这张表在我后来写网络流和树形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的价值不只是那几个模板题，我个人在字符串题里用到得不少。

最长回文子序列就是很典型的区间DP：

dp[i][j] = dp[i+1][j-1] + 2, if s[i] == s[j] dp[i][j] = max(dp[i+1][j], dp[i][j-1]), otherwise

还有一类题是“两个序列合并成一个，求最小编辑代价”，如果操作只能在相邻位置进行，也往往会在区间上推。更远的迁移是树结构：树的 DFS 序本身就是一个区间，树上某些剖分问题等价于区间DP。比如“给一棵树加括号”“网络拓扑合并问题”，本质上都是把一段连续区间不断合并成更小的问题。

我在实际训练中形成了一套自己的做题顺序：先确定是否满足区间DP三大特征，再写出dp[i][j]含义，然后写记忆化版本验证正确性，最后换成递推并检查边界。这个流程让我从“看着石子合并答案都费劲”变成“看到区间合并就能快速建模”。如果你正在被区间DP卡住，不妨也试试这个顺序：先别急着背模板，找一道题把记忆化版本写到 AC，然后手动改成递推，体会两种写法下状态依赖的不同。等你能流畅地说清楚“为什么长度循环可以保证子区间已经算完”，这一关就算真正过了。