石子合并（区间 DP）
动态规划 · 区间由短及长 · 枚举分割点
贪心为什么会错
4 堆石子 [4, 1, 3, 2] 排成一行，每次只能合并相邻两堆、代价 = 两堆之和，求合成一堆的最小总代价。直觉贪心「每次挑最小的一对」：先合 1+3？可它们的合并结果会反复参与后续合并——早合的堆被「搬运」次数更多，局部最小不等于全局最小。
把区间当阶段
设 dp[i][j] = 合并第 i..j 堆的最小代价。最后一次合并一定把区间劈成两半：dp[i][j] = mink(dp[i][k] + dp[k+1][j]) + sum(i..j)——枚举分割点 k，再加上「最后把两半合起来」的代价（恰为区间和）。填表按区间长度由短及长：对角线 0 → 相邻直合 → 越来越长。下面的上三角表逐格点亮，黄格是当前格引用的最优拆分对。右侧代码随每一步同步高亮。
| 4 | 1 | 3 | 2 | |
|---|---|---|---|---|
| 4 | 0 | |||
| 1 | 0 | |||
| 3 | 0 | |||
| 2 | 0 |
4 堆石子 [4, 1, 3, 2]，每次只能合并相邻两堆、代价 = 两堆之和，求合成一堆的最小总代价。贪心「每次挑最小」会错——用区间 DP：dp[i][j] = 合并第 i..j 堆的最小代价，对角线自己合自己 = 0
1function stoneMerge(a: number[]): number {
2 const n = a.length;
3 const pre = [0];
4 for (const x of a) pre.push(pre[pre.length - 1] + x);
5 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
6 for (let len = 2; len <= n; len++) // 区间由短及长
7 for (let i = 0; i + len - 1 < n; i++) {
8 const j = i + len - 1;
9 dp[i][j] = Infinity;
10 for (let k = i; k < j; k++) // 枚举分割点
11 dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
12 dp[i][j] += pre[j + 1] - pre[i]; // 本次合并代价 = 区间和
13 }
14 return dp[0][n - 1];
15}
石堆[4, 1, 3, 2]
1 / 8
区间 DP 范式
三层循环：len 由短及长 → 左端点 i → 分割点 k，O(n³)。
为什么由短及长：算 dp[i][j] 时它引用的都是更短区间——填表序保证「用到时已就绪」。
环形变体：石子围成圈 → 拆环成链（复制一倍），答案取 min。
更快：四边形不等式（决策单调性）可把 O(n³) 优化到 O(n²)。
为什么由短及长：算 dp[i][j] 时它引用的都是更短区间——填表序保证「用到时已就绪」。
环形变体：石子围成圈 → 拆环成链（复制一倍），答案取 min。
更快：四边形不等式（决策单调性）可把 O(n³) 优化到 O(n²)。
同一范式的题排成一串：矩阵链乘法（怎么加括号乘法次数最少）、最优二叉搜索树、能量项链、多边形三角剖分——凡是「最后一步把区间劈成两半」的问题，都是石子合并换皮。与LCS、编辑距离同为二维表 DP，只是填表方向从「左上往右下」换成了「短区间往长区间」。