本讲定位：前三讲的 DP 都是”从左往右”沿下标推进的。但有一类问题——合并、消除、配对——它们的最优决策发生在区间中间，从左往右根本推不动。本讲学习一种全新的填表顺序：按区间长度从小到大。
前置知识：专题一（填表顺序由依赖方向决定）、前缀和。
标注 ⭐ 的小节为进阶内容。
石子合并（线性版）：$n$ 堆石子排成一排，每次只能合并相邻两堆，代价为两堆石子数之和，求把所有石子合并成一堆的最小总代价。
先试试老办法：设 $f[i]$ 为”合并前 $i$ 堆的最小代价”？立刻卡住——前 $i$ 堆合出来的那一堆，接下来还要和第 $i+1$ 堆合并，而合并代价取决于石子总数……更糟的是，最优方案未必先把前缀合完（可能先合中间两堆）。决策不再沿着下标单向推进。
换个角度看最终时刻：最后一次合并，一定是把某两大堆合成一堆；这两大堆分别由一段连续区间的石子合成（相邻合并保证了连续性）。也就是说，存在一个分界点 $k$：左边 $[i, k]$ 先自己合成一堆、右边 $[k+1, j]$ 先自己合成一堆，最后两堆相合。
子问题的形状是”区间”——这就是区间 DP 的信号。定义：
$$ f[i][j] = \text{把区间 } [i, j] \text{ 的石子合并成一堆的最小代价} $$
枚举最后一次合并的分界点 $k$：
$$ f[i][j] = \min_{i \le k < j}\Big(f[i][k] + f[k+1][j]\Big) + \text{sum}(i, j) $$
其中 $\text{sum}(i,j)$ 是区间石子总数（最后一次合并的代价），用前缀和 $s$ 做到 $O(1)$：$\text{sum}(i,j) = s_j - s_{i-1}$。边界 $f[i][i] = 0$（单独一堆无需合并）。
$f[i][j]$ 依赖的 $f[i][k]$、$f[k+1][j]$ 都是更短的区间。按专题一的原则——转移用到谁，谁就先算——所以外层循环是区间长度 $len$，从 $2$ 到 $n$：
#include<bits/stdc++.h>
using namespace std;
int a[305];
long long s[305], f[305][305]; // f[i][j]：合并区间 [i,j] 的最小代价
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i]; // 前缀和：区间和 O(1)
}
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++) f[i][i] = 0; // 单堆不用合并，代价 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++) // 枚举最后一次合并的分界
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
printf("%lld\n", f[1][n]);
return 0;
}
这三层循环就是区间 DP 的标准模板：长度 → 左端点 → 分界点，复杂度 $O(n^3)$。这个立方复杂度决定了区间 DP 的典型数据范围是 $n \le$ 几百，看到 $n \le 300$ 左右的”合并/消除”题，先想区间 DP。
辨析：为什么合并果子（P1090）用贪心，石子合并必须 DP？ 合并果子任取两堆合并，无相邻限制，交换论证可证”每次取最小两堆”最优（哈夫曼）；石子合并只能相邻合并，贪心反例俯拾即是，必须枚举所有分界。约束的一字之差，决定算法的天壤之别——这是极好的课堂讨论素材。
题意：$n \le 100$ 堆石子围成一圈，相邻可合并，分别求合并成一堆的最小与最大总代价。
样例：
4 5 9 4→ 最小43，最大54。