状态不再是"第几个数"，而是"一整段区间"——枚举一个分割点，把区间拆成两半分别求解，再合并起来。
13 模块讲过的线性 DP，状态通常是"到第 i 个位置为止"；区间 DP 的状态则是一整段区间 [l, r]，常见于"把一段序列不断合并/分割，求最优代价"这类问题——比如把一排石子堆不断合并成一堆、把一个字符串通过插入字符变成回文串、给一串矩阵加括号求最少乘法次数。这类问题的共同点是：一段区间的最优解，可以通过枚举一个分割点，拆成两个更小的子区间分别求解，再合并起来。
设 dp[l][r] 表示区间 [l, r] 的最优解。枚举一个分割点 k（l ≤ k < r），把 [l,r] 拆成 [l,k] 和 [k+1,r] 两段，这两段各自的最优解是 dp[l][k] 和 dp[k+1][r]（已经算好），再加上"合并这两段"本身需要付出的代价，取所有分割点里最优的一种：
| 要素 | 区间 DP 里对应什么 |
|---|---|
| 状态定义 | dp[l][r]：区间 [l,r] 的最优解（具体含义因题目而异） |
| 转移方程 | dp[l][r] = min{ dp[l][k] + dp[k+1][r] + cost(l,r) }，枚举 k∈[l,r-1] |
| 初始化 | dp[i][i] = 0（区间只有一个元素，不需要合并，没有代价） |
| 填表顺序 | 按区间长度从小到大——先算长度为 2 的区间，再算长度为 3 的……（见 ⑥ 陷阱） |
石子合并：有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价等于这两堆石子数之和，合并后的新堆数量就是这两堆之和。反复合并直到只剩一堆，求最小的总代价。用 a = [1, 3, 5, 2]（4 堆）演示：
这里的 cost(l,r)（合并 [l,r] 这一段最后一步的代价）就是这一段石子的总和——用 5.1 节的前缀和可以 O(1) 算出：prefix = [0,1,4,9,11]，sum(l,r) = prefix[r]-prefix[l-1]。
| r=1 | r=2 | r=3 | r=4 | |
|---|---|---|---|---|
| l=1 | 0 | 4 | 13 | 22 |
| l=2 | 0 | 8 | 17 | |
| l=3 | 0 | 7 | ||
| l=4 | 0 |
dp[i][i]=0 是初始化的起点。以 dp[1][4]（合并全部 4 堆的最小代价）为例，枚举分割点 k=1,2,3：k=1: dp[1][1]+dp[2][4]+sum(1,4)=0+17+11=28；k=2: dp[1][2]+dp[3][4]+sum(1,4)=4+7+11=22；k=3: dp[1][3]+dp[4][4]+sum(1,4)=13+0+11=24。三者取最小，dp[1][4]=22，在 k=2 处取得。对应的实际合并方案是：先把 [1,3,5,2] 分成左边 [1,3] 和右边 [5,2] 两组，各自先合并成一堆（代价 4 和 7），再把这两堆合并（代价 4+7=11），总代价 4+7+11=22。| 1 | int a[MAXN], prefix[MAXN], dp[MAXN][MAXN], n; |
| 2 | |
| 3 | int Sum(int l, int r) { return prefix[r] - prefix[l-1]; } |
| 4 | |
| 5 | int IntervalDP() |
| 6 | { |
| 7 | for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + a[i]; |
| 8 | // dp[i][i] = 0 全局数组默认已经是 0，不需要手动初始化 |
| 9 | |
| 10 | for (int len = 2; len <= n; len++) // ★ 按区间长度从小到大枚举 |
| 11 | { |
| 12 | for (int l = 1; l + len - 1 <= n; l++) |
| 13 | { |
| 14 | int r = l + len - 1; // 由左端点 l 和长度 len 推出右端点 r |
| 15 | dp[l][r] = 1e9; |
| 16 | for (int k = l; k < r; k++) // 枚举分割点 |
| 17 | dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + Sum(l, r)); |
| 18 | } |
| 19 | } |
| 20 | return dp[1][n]; |
| 21 | } |
len 决定"先算短区间、再算长区间"这个填表顺序；中间层 l 枚举这个长度下所有可能的起点（r 由 l+len-1 直接算出，不需要单独循环）；最内层 k 枚举分割点。dp[l][k] 和 dp[k+1][r] 的区间长度都严格小于 len，按外层循环的顺序，这两个值必然已经算好。状态数是 O(n²)（l、r 各 n 种取值），每个状态转移要枚举分割点 k，O(n)。整体时间复杂度 O(n³)——比线性 DP 慢一个数量级，n 通常不会太大（几百到一千出头比较常见）。
for(l=1;l<=n;l++) for(r=l;r<=n;r++)，在算 dp[1][4] 时可能 dp[2][4] 还没被算过（因为 r 的内层循环还没跑到需要的组合），导致用到了未初始化的脏数据。正确做法是按区间长度 len 从小到大作为最外层循环，确保用到的子区间一定是"更短的、已经算好的"。cost(l,r) 本身需要 O(n) 现场累加（而不是像本节这样用前缀和 O(1) 查询），整体复杂度会从 O(n³) 恶化成 O(n⁴)，在数据规模稍大时就会超时。dp[l][r] = 1e9 是求最小值时的"正无穷"占位，如果题目求的是最大值，要改成一个足够小的负数；如果忘记初始化、或者初始化成 0，min／max 比较时会被这个错误的初始值污染，导致结果不正确。