区间 DP：石子合并

1 一句话问题

n 堆石子排成一排，每次只能合并相邻的两堆，代价是这两堆石子数之和。 求把所有石子合并成一堆的最小总代价。

2 先用手算一遍：五个数字，贯穿全章

石子： 4 1 2 3 5        （5 堆，一共 15 颗）

先想清楚一件事：不管怎么合，最后那一次合并的代价恒等于 15（把整排并成一堆）。 所以能省的只有前面几步。

• 正确答案 33：先合 1+2=3，再合 4+3=7，另一边合 3+5=8，最后 7+8=15。 总代价 3 + 7 + 8 + 15 = 33。
• 贪心（每次合最小的相邻两堆）34：它第一步也合 1+2，第二步就分家了 —— 第 10 步细看。
• 后面三个数字是三份写错的代码跑出来的，每一个都对应一类典型错误： 15（填表顺序写错）、20（前缀和差一）、35（断点范围差一）。

33 / 34 / 15 / 20 / 35 —— 这五个数后面每一步都会回来验。

3 暴力：真的一步步合，(n-1)! 条路径

点「运行 ▶」看结果

它手里拿着当前这一排堆，挑一对相邻的合掉，然后接着挑。 第一步有 n-1 对可选，合完剩 n-1 堆于是又有 n-2 对…… 一共 (n-1)! 条路径。

跑出来 33，和手算一致。

4 实测：它慢得非常有节奏

本机实测（./genBig n，固定种子）：

最后一列就是阶乘的样子：每加一堆，暴力乘以当前的堆数。 而 DP 那一列压根没动 —— 它是 n³，从 10 堆到 13 堆只从 1000 涨到 2197 次转移，量都量不出来。

5 慢在哪：一样的区间，被重复算了成千上万遍

盯住暴力的搜索树：先合 (1,2) 再合 (4,5)，和先合 (4,5) 再合 (1,2) —— 走到这两条路的尽头时，手里的局面一模一样，后面要做的事也一模一样， 可暴力把它们从头到尾各算了一遍。

这正是第 17 章那个「重复子问题」，一个字都没变。于是：

f[l][r] = 把第 l 堆到第 r 堆合并成一堆，最少要付多少代价

f[l][r] = min{ f[l][k] + f[k+1][r] }  +  (a[l] + … + a[r])
           k ∈ [l, r-1]

6 先写记忆化搜索 —— 它根本不用你操心顺序

点「运行 ▶」看结果

跑出来 33。而且注意：这份代码里没有任何「顺序」的痕迹。

solve(l, r) 要用 solve(l, k) 和 solve(k+1, r)，就直接递归下去要 —— 谁先算谁后算，是递归自己安排的，你一个字都不用想。

7 ★ 关键一步：按区间长度从小到大

for (int len = 2; len <= n; len++)              // ★ ① 先枚举区间长度，从短到长
    for (int l = 1; l + len - 1 <= n; l++) {    //   ② 再枚举左端点
        int r = l + len - 1;
        long long best = LLONG_MAX;
        for (int k = l; k < r; k++)             //   ③ 最后枚举断点
            best = min(best, f[l][k] + f[k + 1][r]);
        f[l][r] = best + s[r] - s[l - 1];
    }

点「运行 ▶」看结果

还是 33。想看它一层一层长起来的样子，就跑这份：

点「运行 ▶」看结果

长度 1 :  f[1][1]=0  f[2][2]=0  f[3][3]=0  f[4][4]=0  f[5][5]=0        <- 地基
长度 2 :  f[1][2]=5(k=1)  f[2][3]=3(k=2)  f[3][4]=5(k=3)  f[4][5]=8(k=4)
长度 3 :  f[1][3]=10(k=1)  f[2][4]=9(k=3)  f[3][5]=15(k=4)
长度 4 :  f[1][4]=19(k=1)  f[2][5]=20(k=4)
长度 5 :  f[1][5]=33(k=3)

每一层用到的都只是下面那些层的值。 这就是「按区间长度从小到大」的全部含义。 （check:viz 拿这张表和动画逐格对过，包括每一格选中的断点 k，不只比最终答案。）

8 ★ 关键一步（二）：判据是依赖，不是那个写法

几乎所有资料都会告诉你「区间 DP 就是要按长度枚举」。这句话能用，但它说小了。 下面这份代码看着一点都不像区间 DP —— 它是对的：

点「运行 ▶」看结果

跑出来还是 33。为什么？还是拿依赖去对：

两个依赖都在手上，所以它和按长度枚举一模一样。 check:viz 拿 300 组随机数据钉死了这一条：它的「被抓轮数」是 0 / 300 —— 不是数据不够狠，是它根本没错（第 25 章那份 vol2In.cpp 是同一件事）。

反过来，把左端点写成正序：

点「运行 ▶」看结果

跑出来 15 —— 正是这排石子的总数。

把三种顺序摆在一起，顺便把「错在哪」数出来：

点「运行 ▶」看结果

  填表顺序                      答案   读到还没算好的格子   和正解一样
  ----------------------------  ----   ------------------   ----------
  按区间长度从小到大              33                    0   是
  左端点倒序、右端点正序          33                    0   是
  左端点正序、右端点正序          15                   10   否

这份代码给每一格挂了一个「算好了没有」的标记，转移时只要读到没算好的就计一次数。 于是「顺序错了」不再是一句抽象的话，它是一个数字。

9 动画：三角形的表，一层一层往上长

每一行是左端点 l，每一列是右端点 r，只有右上半张表有意义 —— 所以它是个三角形。 浅绿的对角线是长度 1 的区间（代价 0），那是地基。

蓝色 = 正在填的格子，它的两个来源会被标成 绿色（已经算好） 或 红色（还没算好）。

盯住左下角那个计数器「读到还没算好的格子」：

红色一出现，读到的就是初值 0，这一格的答案立刻变成假的 —— 而程序不会有任何反应。这个计数器也参与交叉验证（防止「答案蒙对、过程画错」）。

10 ★ 打一次假：那个「每次合最小的相邻两堆」的贪心

这是这道题最经典的错误直觉，而且它错得很有来头（第 1 步那个 ⚠）。

点「运行 ▶」看结果

跑出来 34，比正解多 1。多的这 1 是怎么丢的？看动画：

那这个贪心到底有多错？错得罕见还是错得普遍？别猜，枚举一遍：

点「运行 ▶」看结果

  堆数   枚举组数   反例组数     占比   最小反例（字典序最小）   贪心 / 正解
  ----   --------   --------   ------   ----------------------   -----------
     3        216          0     0.0%   （一个都没有）           贪心永远是对的
     4       1296        105     8.1%   2 2 1 2                  15 / 14
     5       7776       1224    15.7%   1 1 2 1 2                17 / 16
     6      46656      10540    22.6%   1 1 1 1 1 2              19 / 18

这张表（第 20 章 coinFind.cpp 的同款做法）一口气回答了三件事：

1. 最小反例是 2 2 1 2（贪心 15、正解 14）—— 动画里有个按钮可以直接切过去看。
2. 反例占比就是「随手造一组数据能抓住它」的概率。4 堆时只有 8.1%， 所以样例过了什么都证明不了。
3. ★ 3 堆时反例是 0 —— 那时候这个贪心是真的对的。

11 顺便把第 23 章欠的账还了：输出合并方案

第 23 章末尾说过一句话：「要方案就得开二维表」。一维滚动数组只留得下答案， 留不下「这个答案是怎么来的」。

区间 DP 的 f 本来就是二维的，所以这笔账还起来特别便宜 —— 只要再开一张同样大的 from[l][r] 记下最优断点：

点「运行 ▶」看结果

最小总代价 = 33

  第几次   合并的两段        代价   合并后这一排
  ------   ---------------   ----   ------------------------
       1   [2,2] + [3,3]        3   4 3 3 5
       2   [1,1] + [2,3]        7   7 3 5
       3   [4,4] + [5,5]        8   7 8
       4   [1,3] + [4,5]       15   15

12 ★ 对拍：以及一次「我的两个直觉都错了」的现场记录

300 轮实测，五个版本：

13 这一章可以带走的四样东西

14 自测