子问题视角：分治与动态规划
区间 DP
认出它：状态是「一段区间」
前面几类 DP 的状态都是「前 i 个」或「以 i 结尾」—— 子序列问题那两套模板都是一维推进。
区间 DP 不一样：dp[i][j] 表示原数组 [i..j] 这一段的答案，
转移是枚举一个分割点 k，把大区间拆成两个小区间：
dp[i][j] = 最优{ dp[i][k] + dp[k+1][j] + 合并这两段的代价 }
k 从 i 到 j-1⭐ 判据很好用：如果「把两段的答案拼起来」需要知道两段的边界值， 而不只是两段各自的结果 —— 那就是区间 DP。
典型信号：
- 题面里有「合并」「切分」「消除」「戳破」这类操作
- 操作的顺序会影响总代价
- 数据范围小（n ≤ 500 左右）—— 因为它是 O(n³)
🚨 遍历顺序：这是区间 DP 唯一的机械难点
dp[i][j] 依赖 dp[i][k] 和 dp[k+1][j]，这两个都是更短的区间。
所以必须保证「短的先算」。两种写法：
// 写法一：按区间长度递增（最直观）
for (let len = 2; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
// ...
}
// 写法二：i 从大到小，j 从小到大
for (let i = n - 1; i >= 0; i--)
for (let j = i + 1; j < n; j++) {
// ...
}🚨 写法二里的 i 必须倒序。 因为 dp[i][j] 要读 dp[i+1][...] ——
那是「下面一行」，正序的话还没算。
⚠️ 写错的症状：不报错，答案偏小
拿最长回文子序列试
（它也是区间 DP，dp[i][j] = s[i..j] 里最长回文子序列的长度）：
输入 正确 i 写成正序
"bbbab" 4 2
"cbbd" 2 1
"aabaa" 5 2
"character" 5 2⚠️ 没有越界、没有异常。正序时它去读「下面一行」，而那一行还没算 ——
拿 "bbbab" 数一遍它读到了什么：
读到 0（还没算的格子） 13 次
读到 1（对角线的 base case） 7 次
读到任何算好的值 0 次 ← 一个都没有于是每一步都少加一截，答案系统性偏小。5000 组随机串实测：
偏小 3671 组 = 73.4%
相等 1329 组 = 26.6%
偏大 0 组 ← 方向是稳定的🚨 这个错很难自己发现，有两个原因叠在一起：
4 和 2 都是「看起来合理的长度」，而且四分之一的输入上它碰巧算对。
📌 区间 DP 出了错，第一件事就是检查遍历顺序，比检查方程划算得多。
⭐ 戳气球：必须反过来想
这是区间 DP 里最经典、也最反直觉的一道（力扣 312）。
有一排气球，戳破第 i 个得到
nums[i-1] * nums[i] * nums[i+1]枚硬币 （越界当 1）。戳破后左右相邻。求最多能拿多少硬币。
自然的想法：枚举「先戳哪个」
// ❌ 枚举第一个戳破的，左右当成独立子问题
for (let k = 0; k < arr.length; k++) {
best = max(best, coin(k) + solve(left) + solve(right));
}这是错的。 实测 [3,1,5,8]：
正确答案 167
「枚举先戳哪个」 66
贪心「每次戳收益最大的」 96🚨 错在子问题不独立。戳破 k 之后，左半和右半的气球会相邻起来 —— 左半最后剩下的那个，它的右邻居来自右半。 把两边当成独立区间（边界补 1），就丢掉了这个耦合。
⚠️ 注意上表里一个反直觉的地方：「枚举先戳哪个」比无脑贪心还差（66 < 96）。 1500 组随机输入也是这个方向：
偏小的比例 偏小时平均只有正确答案的
「枚举先戳哪个」 77.5% 58.6%
贪心「戳收益最大的」 64.8% 82.8%⭐ 「看起来更像动态规划」不等于更接近正确。 把子问题拆错，比根本不拆（贪心）还糟 —— 错误的状态定义会把一大片可行解直接排除掉，而贪心至少还在真实的解空间里走。 📌 两种错法都从不给出偏大的答案，所以「答案偏小」这个信号对两者都不区分。
反过来：枚举「最后戳哪个」
⭐ 关键一转：假设 [i..j] 这段里最后戳破的是 k。
那么在戳 k 的那一刻，[i..j] 里只剩它自己，
它的左右邻居一定是 i-1 和 j+1 —— 这两个是区间外的，位置固定。
于是 [i+1..k-1] 和 [k+1..j-1] 就真的独立了。
function maxCoins(nums) {
const n = nums.length;
const a = [1, ...nums, 1]; // ⭐ 两端补 1，省掉边界判断
const dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
// dp[i][j]：开区间 (i, j) 内的气球全部戳破能得到的最大硬币
for (let len = 3; len <= n + 2; len++) // 长度至少 3 才有中间元素
for (let i = 0; i + len - 1 <= n + 1; i++) {
const j = i + len - 1;
for (let k = i + 1; k < j; k++) // 🚨 k 是最后戳破的
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
}
return dp[0][n + 1];
}📌 注意 dp 用的是开区间 (i, j)，所以转移里是 dp[i][k] + dp[k][j]
而不是 dp[i][k-1] + dp[k+1][j] —— k 本身不属于任何子区间，它最后才被戳。
⭐ 这个「正着想子问题耦合，倒着想就独立了」的转换， 是区间 DP 最值钱的一个套路。遇到「操作顺序影响结果」的题， 先试试把「第一步」换成「最后一步」。
石子合并：贪心为什么不行
一排石子堆，每次合并相邻两堆，代价是两堆之和。求全部合并成一堆的最小总代价。
自然的贪心是「每次合并相邻里最小的两堆」。它是错的。
实测 [6, 4, 4, 6]：
贪心：4+4=8 → [6,8,6]，代价 8
6+8=14 → [14,6]，代价 14
14+6=20，代价 20 总计 42
最优：6+4=10 → [10,4,6]，代价 10
4+6=10 → [10,10]，代价 10
10+10=20，代价 20 总计 40⚠️ 差别在于每个石子被计进总代价几次。把两种顺序记账记出来：
贪心 [6, 4, 4, 6] 计入次数 [2, 3, 3, 1] 6·2 + 4·3 + 4·3 + 6·1 = 42
最优 [6, 4, 4, 6] 计入次数 [2, 2, 2, 2] (6+4+4+6)·2 = 40🚨 被算了三次的是中间那两个 4，不是两边的 6 —— 贪心先把它们合掉，这一堆此后每次合并都要再被计一遍。 而最优解让每个石子都恰好参与两次，一个也不多。
⭐ 这就是记账的价值：总代价 = Σ(石子值 × 它被计入的次数)， 所以最小化总代价等价于让大的石子少参与几次合并。 贪心盯着「这一步花多少」，看不见「这一步会让谁在后面被反复计入」。
🚨 更小的反例：[2,2,1,2] —— 贪心 15，最优 14。
[2,2,1,2] 的相邻和： 4 / 3 / 3 最小值 3 出现了两次
相等时取最左 → 15
相等时取最右 → 14 ← 恰好撞上最优连「相等时选哪个」都会影响结果，说明局部信息根本不足以决策。
⚠️ 但也别把贪心想得一无是处 —— 3000 组随机输入里它只错了 13.9%。 八成以上的情况下贪心恰好给出最优解，这正是它危险的地方： 随手测几组全对，提交上去挂在某个特定形状的数据上。
function mergeStones(stones) {
const n = stones.length;
const pre = [0]; // ⭐ 前缀和：O(1) 取区间和
for (const x of stones) pre.push(pre.at(-1) + x);
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + pre[j + 1] - pre[i]);
}
return dp[0][n - 1];
}⭐ 那个 pre[j+1] - pre[i] 就是前缀和：
不管怎么合并，[i..j] 这段最后一次合并的代价恒等于这段的总和。
📌 ⚠️ 贪心和区间 DP 长得很像（都在做局部选择），区别在于： 贪心的选择不需要子问题的结果，区间 DP 的选择必须先知道两个子区间的答案。 贪心那章讲了怎么判断贪心成不成立 —— 判断不了就老实上 DP，O(n³) 在 n ≤ 500 时完全够用。
模板
function intervalDP(arr) {
const n = arr.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
// ① base case：长度为 1 的区间
for (let i = 0; i < n; i++) dp[i][i] = /* 单个元素的答案 */ 0;
// ② 按长度递增
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = /* 初值：求最小用 Infinity，求最大用 -Infinity 或 0 */ Infinity;
// ③ 枚举分割点
for (let k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, j, k));
}
}
}
return dp[0][n - 1];
}三个要填的空：
- base case 是什么 —— 单个元素通常是 0 或 1
dp[i][j]的初值 —— 求最小用Infinity，写成 0 会让答案恒为 0cost(i, j, k)—— 合并代价，这是每道题真正不同的地方
常见题与它们的区别
| 题 | dp[i][j] 的含义 |
分割点 k 的角色 |
|---|---|---|
| 最长回文子序列 | s[i..j] 的答案 |
不枚举 k，只比较两端 |
| 让字符串成为回文的最少插入 | 同上 | 同上 |
| 石子合并 | 合并 [i..j] 的最小代价 |
最后一次合并的切点 |
| 戳气球 | 开区间 (i,j) 的最大硬币 |
最后戳破的那个 |
| 多边形三角剖分 | 顶点 i..j 构成的多边形 | 和 i、j 组成三角形的第三个顶点 |
⭐ 注意最长回文子序列那两行：它虽然是 dp[i][j]，但不枚举分割点 ——
转移只看 s[i] 和 s[j] 相不相等，所以是 O(n²) 不是 O(n³)。
📌 「区间 DP」是状态的形状，不是转移的形状。
数一遍转移次数，两者不只是「同阶」，是精确的组合数：
n LPS 转移次数 n(n+1)/2 石子合并转移次数 C(n+1,3)
20 210 210 1330 1330
100 5050 5050 166650 166650
200 20100 20100 1333300 1333300
n 从 100 翻到 200：LPS ×3.98（平方是 ×4） 石子合并 ×8.00（立方是 ×8）而「数据范围 n ≤ 500」这条也量一下（O(n³) 那一侧）：
n 100 200 400 500 800
耗时 0.3ms 2.6ms 23.4ms 51.8ms 300ms⭐ n = 500 只要五十毫秒，「完全够用」成立；n = 800 就到三百毫秒了。
立方增长很陡 —— 范围从 500 放宽到 800，代价是六倍。
下一步
区间 DP 的状态定义在数组的一段上。 如果原始结构不是数组而是一棵树，状态就定义在节点上 —— 那就是树形 DP。
练习
勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 516. 最长回文子序列中等区间 DP 里最简单的一种：不枚举分割点，只比较两端；拿它练遍历顺序
- 312. 戳气球困难⭐ 本篇主讲。必须枚举「最后戳破的」而不是「先戳破的」，否则子问题不独立
- 1312. 让字符串成为回文串的最少插入次数困难和 516 是一体两面：答案 = n - 最长回文子序列长度，也可以直接区间 DP
- 1039. 多边形三角剖分的最低得分中等分割点 k 是「和 i、j 组成三角形的第三个顶点」，最标准的区间 DP
- 1547. 切棍子的最小成本困难把切点排序后就是石子合并的镜像；注意要在两端补上 0 和 n
- 375. 猜数字大小 II中等⚠️ 求的是「最坏情况下的最小代价」——minimax，别写成求最小值
- 486. 预测赢家中等博弈型区间 DP：dp[i][j] 存「先手比后手多多少」，一个状态装下两个人
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。