小镇物资局的老王遇到一个难题：一条街上开了 5 家水果摊，苹果数分别是 4、3、2、5、1 筐。市里要求把这条街的摊位合并成一家大超市，规则是每天只能合并相邻的两家，合并这一天的搬运成本等于两家苹果筐数之和。老王想找出一种合并顺序，让整个过程的累计搬运成本最小。直觉告诉他，应该先把“小个头”的摊位合并掉，但究竟哪一步先合、哪一步后合，靠瞎试根本试不完。这个问题就是一个典型的区间动态规划问题——在连续一段区间上做决策，大区间的最优解依赖小区间的最优解。本文就用“合并水果摊”与“切蛋糕分给朋友”这对孪生比喻，带零基础的读者完整掌握区间DP的状态定义、转移方程、循环顺序、四边形不等式优化，以及回文子串、戳气球等经典应用。

岗位关联

区间DP是算法面试和工程优化中的高频模型：理解它不仅能手撕石子合并、矩阵连乘这类真题，更能迁移到数据库连接顺序优化、句法分析等真实AI系统中，帮你建立“把大问题拆成可复用子问题”的底层思维。

目录
  1. 可视化演示
  2. 区间DP概述
  3. 状态定义转移
  4. 石子合并问题
  5. 矩阵连乘问题
  6. 循环顺序方向
  7. 四边形不等式优化
  8. 经典应用场景
  9. 代码与复杂度
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示区间DP三大核心：石子合并过程、DP表格对角线填充顺序、矩阵连乘最优分割，步进式演示状态转移方向。

本节配有交互动效（进入视口后自动加载，约 3KB）。

石子合并问题 相邻石子堆逐步合并，代价为两堆之和 合并阶段高亮当前操作堆 总代价最小化为目标

区间DP概述

老王的水果摊是一个绝佳的比喻：摊位排成一条直线，任何一次合并都发生在“相邻两家”之间，所以任何时刻我们处理的都是这条街上连续的一段摊位。如果把目标看成“把第 i 家到第 j 家合并成一家”，那么这场合并的最终结果一定可以划分成两段：左边一段先合并好，右边一段先合并好，最后两家再合并。这就是区间DP的第一个关键认知——决策的对象是连续区间。

如果不懂动态规划，老王会尝试所有合并顺序。5 堆石子有 4 次合并，但不同的合并次序数量是 14 种；增加到 10 堆时，这个数字是 4862 种；到 20 堆时，已经超过 1.7 亿种。这个序列叫卡特兰数，它增长的速度比指数还快。暴力枚举完全不可行，必须利用“子问题的答案可以复用”这一特性。

区间DP的三步设计法因此诞生：第一步定义状态——用 dp[i][j] 描述“把第 i 家到第 j 家合并好”的最优值；第二步写转移——思考最后一次合并发生在哪两个“大块”之间，用更小区间的答案拼出当前答案；第三步定边界——单个摊位不需要合并，所以 dp[i][i] = 0。这三步就像老王制定合并计划时的三张清单：先列摊位段、再选分割点、最后填代价表。理解了这三步，就理解了区间DP的总纲，后面所有内容都在为这三步填入具体细节。

状态定义转移

状态是动态规划的“记账本”。在老王的账本上，dp[i][j] 记的是：把第 i 家水果摊到第 j 家水果摊合并成一家，最少需要多少天。账本是一个二维表，横轴是起点 i，纵轴是终点 j，只有 i ≤ j 的格子有意义。i = j 的格子全是 0——一家摊不需要合并。这张表要按什么顺序填？答案是按区间长度从小往大填。

为什么必须先填短区间？因为“长为 5 的区间的最优解”要用到“长为 2、3、4 的区间的最优解”。如果先填长区间，它依赖的小格子还空着，账本就算不出来。这就像老王必须先安排“两家并一家”的日子，才能安排“三家并一家”的日子，顺序颠倒整个计划就崩了。

转移方程描述的是“最后一步”：假设第 i 到第 j 家在最后一轮合并之前，被分割成左段 i..k 和右段 k+1..j，两段分别已经在之前的日子里合并成了两家，那么最后一天的搬运成本就是两家苹果筐数之和，也就是整段的苹果总数。所以状态转移为：

这段“账本”思想对小白非常重要：先记小账，再记大账，每一次新记录都建立在已有记录之上。区间DP里，状态就是账目格子，转移就是记账规则，循环顺序就是记账顺序。三者齐备，问题自然迎刃而解。

dp[i][j]=min⁡i≤k<j{dp[i][k]+dp[k+1][j]}+∑t=ijat\displaystyle dp[i][j] = \min_{i \le k < j} \Big\{ dp[i][k] + dp[k+1][j] \Big\} + \sum_{t=i}^{j} a_t
这个方程的意思是：左边段的最优成本 + 右边段的最优成本 + 最后一天把两大车苹果搬在一起的成本，取所有分割方式中的最小值。
  1. 状态含义dp[i][j] 表示把第 i 堆到第 j 堆合并成一堆的最少总代价。
    dp[i][j]=min⁡i≤k<j{⋅}+∑t=ijatdp[i][j] = \min_{i \le k < j} \{\cdot\} + \sum_{t=i}^{j} a_t
  2. 分割点 k最后一次合并前，一定有某个位置 k 把区间切成两半，左边已合成一堆，右边也已成一堆。
    k∈[i,j−1]，左段[i,k]，右段[k+1,j]k \in [i, j-1]，左段 [i, k]，右段 [k+1, j]
  3. 左右子问题两段各自的最优合并成本为 dp[i][k] 与 dp[k+1][j]，它们已在更短区间时算好。
    dp[i][k]+dp[k+1][j]dp[i][k] + dp[k+1][j]
  4. 区间总和最后合并时把左右两堆搬在一起，代价等于区间内所有苹果数之和。
    ∑t=ijat=Sj−Si−1\sum_{t=i}^{j} a_t = S_j - S_{i-1}

石子合并问题

让我们把账本真正用在老王的 5 家水果摊上：苹果数分别是 4、3、2、5、1。第一步，先算所有长度为 2 的区间：dp[1][2] = 4 + 3 = 7（把第 1、2 家合并，代价 7）；dp[2][3] = 5；dp[3][4] = 7；dp[4][5] = 6。第二步，算长度为 3 的区间：dp[1][3] 有两种分割，k=1 时 0+dp[2][3]+9 = 14，k=2 时 dp[1][2]+0+9 = 16，取最小 14。就这样一层层从短到长填表，最终 dp[1][5] = 35，这就是最小总搬运成本。可以看到，这个计算过程不需要真的去模拟每一种合并顺序，而是每步只记“最少需要多少天”。

石子合并问题中有个细节值得留意：转移方程里的区间和 sum(i, j) 如果用循环现算，每次要 O(n)，整体复杂度会变成 O(n^4)。聪明的做法是前缀和：预先算出 S[0..n]，其中 S[t] 表示前 t 堆的总数，那么任意区间和一步可得：

预计算前缀和让石子合并的复杂度稳定在 O(n^3)。有趣的是，石子合并还有一种变形——环状石子合并：如果摊位首尾相连成一个环，我们可以把数组复制一份变成 2n 的长度，再在区间长度 n 的所有窗口里取最小值。这就像老王不只管一条街，而是管一个环形广场，他只需要把摊位列表抄一遍贴在另一侧，就能用同样的账本方法解决。这个“复制数组破环为链”的小技巧，在环形区间问题上几乎百试百灵。

sum(i,j)=Sj−Si−1,St=∑r=1tar\displaystyle \text{sum}(i, j) = S_j - S_{i-1}, \quad S_t = \sum_{r=1}^{t} a_r
前缀和就像老王的“库存总账”：他只要记住“到第几家为止一共多少筐”，就能随时口算出任意两家之间的筐数，不需要现场逐家清点。
  1. 前缀和定义S[t] 表示从第 1 家到第 t 家的苹果总筐数，是累计值。
    St=∑r=1tar，其中S0=0S_t = \sum_{r=1}^{t} a_r，其中 S_0 = 0
  2. 区间和换算第 i 家到第 j 家的总量 = 前 j 家的累计量 − 前 i−1 家的累计量。
    Sj−Si−1S_j - S_{i-1}
  3. 代入转移把该式替换转移方程中的求和项，使每次转移 O(1) 完成。
    dp[i][j]=min⁡i≤k<j{dp[i][k]+dp[k+1][j]}+Sj−Si−1\displaystyle dp[i][j] = \min_{i \le k < j}\big\{dp[i][k] + dp[k+1][j]\big\} + S_j - S_{i-1}

矩阵连乘问题

水果摊是“越并越少”，现在换一个对称的场景：老王周末要给朋友们分蛋糕。一块长方形的蛋糕，他想切成 n 小块，切法不同，切痕总长度就不同。这个“切蛋糕”问题对应算法中的矩阵连乘：n 个矩阵 A1, A2, ……, An 要连乘，乘法顺序不同，标量乘法总次数天差地别。比如三个矩阵维度是 10×30、30×5、5×60，先乘前两个需 1500 次，再乘第三个需 3000 次，总共 4500 次；而先乘后两个需 9000 次，再乘第一个要 3000 次，总共 12000 次——同样的结果，代价差了三倍。

矩阵连乘的决策对象同样是“连续的一段矩阵”，从第 i 个乘到第 j 个。最后一次乘法一定是把整个区间分成左右两个大块：左边先乘出一个矩阵，右边先乘出一个矩阵，再把两个矩阵相乘。左右两块的维度由分割点决定，额外代价等于 p[i-1] × p[k] × p[j] 次标量乘法。转移方程和石子合并几乎一模一样，只是把“区间和”换成了“维度乘积”：

切蛋糕场景告诉我们一个深刻结论：合并型问题与分割型问题在数学上同构。石子合并的“最后合并”对应矩阵连乘的“最后一刀”。学会了石子合并的转移框架，矩阵连乘只是换一个代价函数而已。这也提醒小白：与其死记硬背题目，不如看穿问题是“连续区间 + 子问题共享”的本质。

dp[i][j]=min⁡i≤k<j{dp[i][k]+dp[k+1][j]+pi−1×pk×pj}\displaystyle dp[i][j] = \min_{i \le k < j} \Big\{ dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j \Big\}
矩阵连乘是“分割型”区间DP的典型：大区间先切一刀成两半，两边各自最优，再算两半拼起来的额外代价。切割点和合并点是同一枚硬币的两面。
  1. 状态沿用dp[i][j] 表示连乘第 i 到第 j 个矩阵所需的最少标量乘法次数。
    dp[i][j]=min⁡i≤k<j{⋅}dp[i][j] = \min_{i \le k < j}\{\cdot\}
  2. 分割成两块在矩阵 A_k 和 A_{k+1} 之间加一副括号，左边是 [i, k]，右边是 [k+1, j]。
    dp[i][k]+dp[k+1][j]dp[i][k] + dp[k+1][j]
  3. 拼合代价左边算出的矩阵维度是 p[i-1] × p[k]，右边是 p[k] × p[j]，相乘需要 p[i-1]×p[k]×p[j] 次。
    pi−1×pk×pjp_{i-1} \times p_k \times p_j

循环顺序方向

很多初学者把循环写成“先 i 后 j”，填表时发现 dp[i][j] 引用的格子还没算出来，结果全错。区间DP的循环顺序有一条铁律：先枚举区间长度 len，再枚举左端点 i，最后枚举分割点 k。右端点 j 由 i + len - 1 直接算出。这条顺序保证了“每次用到的子区间长度一定比当前区间短”，而短区间的结果已经在之前填好。

为什么长度优先而不是端点优先？回到账本比喻：老王记账的规则是“先记最短的账”。如果按起点 i 的顺序记，第 1 行要从 dp[1][1] 记到 dp[1][n]，但 dp[1][5] 依赖 dp[2][5]，后者在第 2 行，还没记到——起点优先会让账本出现“前向引用”，就像贷款记账还没记到收入就记支出一样荒谬。按长度优先则不然：所有长度为 3 的格子，只依赖长度 1 和长度 2 的格子，而它们都已经记好了。形式化地说，转移方向是从短区间流向长区间，这也是“自底向上”的朴素体现。

一个容易混淆的细节是：转移方程用 min，意味着要遍历所有 k。k 从 i 到 j-1 取值，每次都产生一个候选答案，取最小值。这个过程的时间复杂度是 O(len) 的枚举，累加所有区间就是 O(n^3)。如果题目还想输出合并方案，可以在每次更新最优值时用数组 opt[i][j] 记录下当时的 k，最后从 dp[1][n] 出发递归回溯，就能还原出“哪一天合并哪两家”。这就像老王每记一笔账，都在账本角落写个小注：“这一天是从哪个切分点来的”。

四边形不等式优化

老王合并水果摊时发现一个奇怪规律：对于每段摊位，最优分割点似乎随着区间变大“只往右走，从不回头”。比如 dp[1][3] 的最优分割点在 k=1，dp[1][4] 的最优分割点可能在 k=2，但绝不会小于 k=1。这种性质叫决策单调性，而它成立的充分条件之一就是四边形不等式。四边形不等式的形式是：

这个优化为什么有效？因为决策单调性保证每个分割点的枚举区间比原来短，所有 k 的总尝试次数摊还下来是 O(n^2)，整个算法的时间复杂度从 O(n^3) 降到 O(n^2)。对于几百上千堆的大规模石子合并，这是数量级的飞跃。老王发现这个规律后，每天只需要在两个“候选分界”之间做选择，而不是从头到尾试一遍——这正是“老经验”和“算法优化”的完美结合。不过要注意，四边形不等式不是万能药：只有满足上述代价结构的转移才能用，用前必须验证，否则会得到错误答案。

dp[a][c]+dp[b][d]≤dp[a][d]+dp[b][c],a≤b≤c≤d\displaystyle dp[a][c] + dp[b][d] \le dp[a][d] + dp[b][c], \quad a \le b \le c \le d
四边形不等式描述的是“交叉区间之和不超过包含区间之和”的代价结构。满足它时，区间DP的最优分割点具有单调性，可以据此收紧枚举范围。
  1. 四区间不等式对任意嵌套的四个端点，交叉和的代价不大于包含和的代价。
    a≤b≤c≤d，dp[a][c]+dp[b][d]≤dp[a][d]+dp[b][c]a \le b \le c \le d，dp[a][c] + dp[b][d] \le dp[a][d] + dp[b][c]
  2. 决策单调性记 opt[i][j] 为 dp[i][j] 取得最小值时的分割点，则随区间变大分割点不回落。
    opt[i][j−1]≤opt[i][j]≤opt[i+1][j]opt[i][j-1] \le opt[i][j] \le opt[i+1][j]
  3. 枚举收窄分割点 k 不必从 i 扫到 j-1，只需在 opt[i][j-1] 到 opt[i+1][j] 之间尝试。
    k∈[ opt[i][j−1], opt[i+1][j] ]k \in [\,opt[i][j-1],\ opt[i+1][j]\,]

经典应用场景

区间DP的威力远不止水果摊。先看回文子串：给一个字符串，问它有多少个回文子串。定义 dp[i][j] 表示子串 s[i..j] 是否为回文，那么它依赖两侧字符是否相等以及内部 s[i+1..j-1] 是否为回文。这又是一个标准的区间扩展问题——每次把区间两端各扩一个字符，判断依然成立。这与合并水果摊的逻辑完全一致：小区间先判断，大区间用小区间结论拼接。

再看戳气球：一排气球各自带分数，戳破一个气球得到的分数等于它左右相邻气球分数与自身的乘积。问按什么顺序戳，总分最大。若把“最后戳破的气球”看作区间分割点，那么它左右两侧的气球互不影响，可以在子区间内先戳光——这正是分割型区间DP。最后一个被戳的气球就像蛋糕的最后一刀，它的选择决定了两边独立子问题的边界。

最后是两端取数博弈：一排牌，两个玩家轮流从两端拿一张，都足够聪明，问先手最多能拿多少分。设 dp[i][j] 为先手在区间 [i, j] 上能获得的最大优势分，那么他可以从左端拿 a[i]，此后对手在剩区间里对先手形成优势 dp[i+1][j]，于是自己的净得分为 a[i] − dp[i+1][j]；同理从右端拿得 a[j] − dp[i][j-1]，两者取大。这个方程妙在把“对手的策略”也编码进同一张表，依然是一个区间上的递推。三类应用的共同点呼之欲出：只要问题对象是连续一段、子问题的答案能拼接成父问题，区间DP就可能是答案。

代码与复杂度

把以上思想落成代码，核心就是一个三层循环模板。外层枚举区间长度 len 从 2 到 n，中层枚举左端点 i，内层枚举分割点 k。每一次更新都遵循“短区间已算好”的假设。空间上用二维数组 dp[n][n] 存储所有区间答案，时间复杂度 O(n^3)，空间复杂度 O(n^2)。如果结合四边形不等式优化，可以把分割点枚举区间收窄，总体降到 O(n^2)。石子合并的模板如下：

实现时有几个值得注意的细节。第一，dp 表初始化为 0，因为 dp[i][i] = 0，单堆不需要合并。第二，前缀和数组 prefix 长度设为 n+1，prefix[0] = 0，这样访问 prefix[j+1] 不会越界；区间和用 prefix[j+1] − prefix[i] 一步算出。第三，求最小值时 dp[i][j] 要初始化为一个足够大的数（如 float('inf')），否则全 0 的初值会让 min 永远取 0。第四，如果想输出方案，额外维护 cut[i][j] 数组记录使 dp[i][j] 最优的分割点，最后递归打印合并过程。这些细节看似琐碎，却正是从“看懂算法”到“写对代码”之间的关键一步。老王的故事告诉我们：有了正确状态、转移和顺序，剩下的就是细心填表。

python8 行
for length in range(2, n + 1):    for i in range(n - length + 1):        j = i + length - 1        dp[i][j] = inf        total = prefix[j + 1] - prefix[i]        for k in range(i, j):            cost = dp[i][k] + dp[k + 1][j] + total            dp[i][j] = min(dp[i][j], cost)

AI 应用场景

数据库查询优化器

阶段：查询计划生成与成本估算

解决的问题：一条 SQL 往往涉及多张表连接，连接顺序不同，中间结果大小和 IO 成本差异巨大。优化器需要从所有连接顺序中找出成本最小的一种。传统做法是启发式规则，但面对 10 张以上表时规则容易失效。区间DP把“连接哪几张连续的表”当作区间，把“最优连接顺序”当作状态，枚举最后一步连接的分割点，从而系统化地搜索最优连接树。

具体案例：某数据仓库中，一张事实表 join 三张维度表，各表过滤后行数分别为 10 万、1 万、5 千，优化器用区间DP枚举所有加括号方式，选择把最小的维度表先连接，中间结果从 10 亿行降到 500 万行，查询耗时从 12 秒降到 0.8 秒。这与矩阵连乘问题在数学上完全同构。

自然语言句法分析 CKY 算法

阶段：句法树的动态规划解码

解决的问题：给定一句话，如何拆出符合文法的句法树？CKY 算法用区间DP把“句子第 i 到第 j 个词能否由某非终结符推导出来”定义为状态，枚举分割点把区间分成“主语名词短语 + 谓语动词短语”，逐层拼接出整棵句法树。传统递归下降法可能陷入回溯爆炸，而区间DP保证了每个子区间只算一次。

具体案例：在中文依存句法分析器中，句子“这家公司发布了新的产品”被切割为名词短语区间和动词短语区间，每个小区间先独立分析，再组合成完整句法树。相比逐词拼装的贪婪方法，句法正确率从 82% 提升到 91%。这和戳气球问题一样，都是“选一个分割点，左右独立求解”的思维。

视频拼接的最优剪切点选择

阶段：视频后处理管线

解决的问题：把一段长视频按场景切分成若干片段，再按新脚本重新拼接。每个相邻片段之间的拼接点选择决定了画面跳变幅度，总跳变代价要最小。区间DP把“从第 i 个镜头拼到第 j 个镜头”当作区间，枚举最后拼接的分割点，等价于合并型石子问题——代价从“苹果数之和”换成“镜头间跳变分数”。

具体案例：某短视频平台自动剪辑系统将 40 个镜头拼接为 15 秒成片，用区间DP枚举所有拼接顺序，选出累计跳变代价最小的方案，用户留存率比随机拼接提升 17%。AI 生成视频后处理阶段，这类区间优化还能迁移到音频淡入淡出、图像序列融合等场景。

Python 演示

python39 行
def stone_merge(stones):    n = len(stones)    if n <= 1:        return 0, []    prefix = [0] * (n + 1)    for i in range(n):        prefix[i + 1] = prefix[i] + stones[i]    dp = [[0] * n for _ in range(n)]    cut = [[-1] * n for _ in range(n)]    INF = float('inf')    for length in range(2, n + 1):        for i in range(n - length + 1):            j = i + length - 1            total = prefix[j + 1] - prefix[i]            dp[i][j] = INF            for k in range(i, j):                cand = dp[i][k] + dp[k + 1][j] + total                if cand < dp[i][j]:                    dp[i][j] = cand                    cut[i][j] = k    return dp[0][n - 1], cut  def print_merge_plan(cut, i, j, stones):    if i == j:        return [stones[i]]    k = cut[i][j]    left = print_merge_plan(cut, i, k, stones)    right = print_merge_plan(cut, k + 1, j, stones)    print("merge", left, "and", right)    return [sum(left) + sum(right)]  if __name__ == "__main__":    example = [4, 3, 2, 5, 1]    min_cost, cut_table = stone_merge(example)    print("minimum cost:", min_cost)    print("merge plan:")    print_merge_plan(cut_table, 0, len(example) - 1, example)
目的：完整实现石子合并区间DP，输出最小合并代价，并回溯打印具体的合并步骤（哪两段先合并）。
  1. prefix[i + 1] = prefix[i] + stones[i]构建前缀和数组，让后面任意区间和一步算完，避免每次转移都循环求和。
  2. dp = [[0] * n for _ in range(n)]初始化二维状态表，所有单堆区间默认代价为 0。
  3. for length in range(2, n + 1)外层先枚举区间长度，保证所有子区间比当前区间短、已经算好。
  4. total = prefix[j + 1] - prefix[i]用前缀和 O(1) 求出当前区间苹果总数，这是每次合并最后一轮的成本。
  5. for k in range(i, j)内层枚举分割点，把区间切成左段 [i, k] 和右段 [k+1, j]。
  6. cand = dp[i][k] + dp[k+1][j] + total当前分割方式的总成本 = 左段最优 + 右段最优 + 整段合并成本。
  7. cut[i][j] = k记录最优分割点，供后续回溯打印合并方案使用。
  8. return dp[0][n - 1], cut返回整个区间的最优代价与分割点表，二者配合即可还原完整方案。

常见误区

误区区间DP只能解决“把相邻的东西合并成一堆”的问题，像矩阵连乘这种“把一个东西切开”的问题应该用别的算法。

正解合并和分割本质是一体两面。合并型问题是“最后一步把两段拼起来”，分割型问题是“最后一步把一段切成两半再分别处理”，两者最优子结构完全一致。比如戳气球最后戳破的那个气球，就是“最后的合并点”反过来看。理解这一点，就能把一套转移框架迁移到大量题目上。

为何常见：教材通常从石子合并讲起，导致初学者把区间DP的印象固化为“合并”，忽略了它更本质的“区间上的最优子结构”特征。

误区外层循环只要把 i 从 0 到 n、j 从 i 到 n 扫一遍就行，反正二维表总能填满。

正解如果外层先枚举 i，那么计算 dp[i][j] 时，dp[k+1][j]（k+1 > i）可能还没算过，直接读到初始值 0，答案全错。必须外层枚举区间长度、内层枚举左端点，确保任何被依赖的子区间长度严格更短。可以这样检查：写下转移方程，看它引用了哪些区间，再确认这些区间都先于当前区间被填好。

为何常见：线性DP里 for i: for j: dp[i][j] = dp[i-1][j-1] + ... 是合理顺序，初学者把这种习惯带进区间DP，忽略了区间DP的依赖方向是“短→长”而非“左→右”。

误区四边形不等式优化能把 O(n^3) 降到 O(n^2)，所以任何区间DP我都可以直接用它，省事又高效。

正解四边形不等式有严格使用前提：代价函数必须满足四边形不等式且具有单调性，否则最优分割点的单调性不成立，强行收窄 k 的枚举范围会得到错误结果。正确做法是先验证代价结构（例如 sum(i,j) 满足四边形不等式），再决定是否套用优化。如果题目数据量小，直接 O(n^3) 也是完全安全的。

为何常见：网上题解往往直接写“四边形不等式优化”结论，很少解释推导过程，初学者只见“优化”二字，忽略它背后的数学约束。

误区区间DP不就是把所有可能的合并顺序都试一遍吗？我递归枚举也能得到正确答案，只是慢点。

正解区间DP的核心价值在于子问题复用。暴力枚举 20 堆石子需要 1.7 亿种顺序，而区间DP只计算 O(n^2) 个子区间状态，每个状态只需 O(n) 次比较，总计算量约 O(n^3)。两者结果的正确性相同，但递归枚举不做记忆化时会呈现指数级膨胀，无法在大规模输入上运行。记忆化搜索（自顶向下）虽然也可以，但自底向上的循环写法更简洁也更好掌控顺序。

为何常见：初学者先学递归枚举，再学DP，容易把DP看成“带剪枝的枚举”，忽略了它在状态空间上做“重叠合并”的本质。

误区转移方程里的 sum(i, j) 每次用循环现算，代码照样能跑出正确答案，效率无所谓。

正解如果 sum(i, j) 在每次转移时用循环求和，每个状态要多付出 O(n) 的开销，总复杂度从 O(n^3) 变成 O(n^4)。而一旦 n 到 500 以上，O(n^4) 会慢到无法接受。用前缀和把区间和变成 O(1) 查询是石子合并的标准配套操作，也是从“算得对”走向“算得快”的关键一步。

为何常见：小数据测试时 O(n^4) 也能秒出结果，让初学者误以为“没优化也很轻松”，直到数据量上来才意识到问题。

面试题

Q1. 下列哪种问题特征最适合使用区间DP？

单选题 · easy

  • A.决策对象是连续的一段区间，且大区间依赖小区间结果← 正确答案
  • B.问题只涉及单个变量，状态是线性递推
  • C.决策对象是互相独立的元素，彼此无顺序关系
  • D.只需要贪心选择局部最优即可得到全局最优

答案：A。区间DP的核心标志是“连续区间 + 重叠子问题”。A 正是水果摊合并的场景：每次合并相邻摊位，任何大区间的答案都由两个小区间拼出。B 是线性DP，C 是独立子问题，D 是贪心算法，它们都不需要区间维度的状态。

Q2. 石子合并问题中，状态 dp[i][j] 表示什么？

单选题 · easy

  • A.前 i 堆石子合并成 j 堆的最小代价
  • B.第 i 堆到第 j 堆石子合并成一堆的最小代价← 正确答案
  • C.第 i 堆与第 j 堆两堆合并的代价
  • D.第 i 堆到第 j 堆石子的总重量

答案：B。dp[i][j] 的物理含义是把连续的第 i 堆到第 j 堆合并成一堆所需的最小代价。A 混淆了“前 i 堆”和“第 i 到第 j 堆”；C 只描述了一次合并；D 是区间和，是转移方程里的一个加项，而不是状态本身。

Q3. 朴素区间DP求解石子合并的时间复杂度和空间复杂度分别是？

单选题 · easy

  • A.O(n^2) 和 O(n)
  • B.O(n^3) 和 O(n)
  • C.O(n^3) 和 O(n^2)← 正确答案
  • D.O(n^2) 和 O(n^2)

答案：C。三重循环（长度、左端点、分割点）对应 O(n^3)；二维 dp 表存储所有区间答案，空间 O(n^2)。O(n^2) 的时间是四边形不等式优化后的复杂度，不能用在此题。空间 O(n) 需要滚动数组优化，但区间DP常用二维表回溯方案。

Q4. 区间DP的循环为什么必须先枚举区间长度，再枚举左端点？

单选题 · mid

  • A.保证计算当前区间时，所有依赖的子区间已经算好← 正确答案
  • B.先枚举长度可以压缩代码行数
  • C.为了配合贪心策略使用
  • D.枚举顺序对结果没有影响，只是风格差异

答案：A。dp[i][j] 依赖 dp[i][k] 和 dp[k+1][j]，这两个子区间的长度都小于 j-i+1。按长度从小到大枚举，能保证转移动态规划里的依赖总是落在已算好的格子上。若先枚举左端点 i，计算 dp[i][j] 时 dp[k+1][j] 可能还没被填，答案就会错误。这和记账时“先记小账、再记大账”是一个道理。

Q5. 矩阵连乘问题与石子合并问题的关系是？

单选题 · mid

  • A.两者毫无关系，是两种完全不同的算法
  • B.矩阵连乘是分割型问题，石子合并且合并型，但状态转移结构同构← 正确答案
  • C.矩阵连乘只能用贪心求解，石子合并才能用DP
  • D.矩阵连乘的复杂度比石子合并低一个数量级

答案：B。矩阵连乘是“最后一刀”把区间切成两半，两边各自最优解再加拼合代价；石子合并是“最后一步”把两半合并，两边各自最优解加区间和。两者状态定义、循环结构、分割点枚举方式完全一致，只是额外代价函数不同。正如切蛋糕与拼蛋糕在数学上对称。

Q6. 下列哪些问题可以用区间DP求解？

多选题 · mid

  • A.统计一个字符串中回文子串的个数← 正确答案
  • B.戳破一排气球，求最大得分← 正确答案
  • C.求有向图中两点的最短路径
  • D.两个玩家从牌堆两端轮流取牌，求先手最大得分← 正确答案

答案：ABD。回文子串通过区间两端扩展判断，戳气球把最后戳破的气球当作分割点，两端取牌用区间优势差递推，三者都是“连续区间 + 子问题拼接”，是标准的区间DP。最短路径用 Dijkstra 或 Floyd，与区间无关。

Q7. 关于四边形不等式优化，下列说法正确的有？

多选题 · mid

  • A.需要状态满足四边形不等式条件← 正确答案
  • B.要求最优分割点具有决策单调性← 正确答案
  • C.任何区间DP都可以无条件套用该优化
  • D.优化后复杂度从 O(n^3) 降至 O(n^2)← 正确答案

答案：ABD。四边形不等式优化的前提是代价函数满足四边形不等式，从而推出最优分割点单调，枚举范围收窄到 opt[i][j-1] 到 opt[i+1][j] 之间，摊还后复杂度从 O(n^3) 降到 O(n^2)。C 是常见误区：条件不满足时强行优化会得到错误答案。

Q8. 石子合并中为什么要使用前缀和？

单选题 · hard

  • A.前缀和能让区间和 sum(i, j) 在 O(1) 时间内求出← 正确答案
  • B.前缀和是石子合并唯一正确的实现方式
  • C.前缀和可以把时间复杂度降到 O(n)
  • D.前缀和用来记录已经合并过的石子堆编号

答案：A。转移方程中每次都要计算区间和，前缀和将区间和转换为 S[j] − S[i-1]，使每次状态转移从 O(n) 降为 O(1)，整体复杂度保持 O(n^3)。B 错误：不用前缀和也能算对，只是变慢；C 错误：整体复杂度仍由三重循环主导；D 与石子合并无关。

Q9. 若石子堆首尾相连成环形，常见的处理手段是什么？

单选题 · hard

  • A.把环复制成 2 倍长度数组，在长度为 n 的窗口内取最小值← 正确答案
  • B.直接把数组反转再合并一次
  • C.环形问题无法用区间DP，必须换算法
  • D.首尾两堆可以同时合并，所以只需 n−1 次

答案：A。环形结构没有固定的起点，常用技巧是把数组复制一份，形成长度 2n 的链，然后对所有长度恰好为 n 的区间执行一次区间DP，最后在这些区间的最优解中取最小值。这相当于穷举了每个可能的“断开点”，再用线性方法求解，是正确的标准做法。

Q10. 关于四边形不等式优化后的实现，以下说法正确的有？

多选题 · extreme

  • A.分割点 k 只在 opt[i][j-1] 到 opt[i+1][j] 之间枚举← 正确答案
  • B.需要额外维护 opt 表记录每个区间的最优分割点← 正确答案
  • C.总复杂度摊还后约为 O(n^2)← 正确答案
  • D.只要数据规模大，任何区间DP套用该优化必然更快且更准

答案：ABC。决策单调性给出 opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]，因此分割点枚举范围收窄；opt 表用于记录和传播最优分割点；因每个分割点被枚举的次数摊还下来是常数，总复杂度约 O(n^2)。D 错误：四边形不等式有适用前提，未验证满足条件时套用会得到错误答案，而非“必然更快更准”。