石子合并（链形）

先看一个具体场景：一排摆着 4 堆石子，数目依次是 $7,\ 6,\ 5,\ 4$。 每次只能挑相邻的两堆并成一堆，代价是这两堆石子数之和。不断合并，直到剩下唯一一堆——不同的合并顺序，累计代价不同，问最小总代价。

第一反应也许是贪心：每次挑当前最小的相邻两堆并。可这在石子合并里并不总对——因为一堆石子会反复参与后续每一次合并，早并的堆，其石子数会被后面一次次重复计入代价。此刻看着便宜的一步，可能把某堆抬进后续昂贵的合并里。 这是个牵一发动全身的全局问题。

那把「先合哪对、再合哪对」的所有顺序都枚举一遍？$n$ 堆的合并顺序数量随 $n$ 指数爆炸，不可行。 但换个角度：无论怎么合，最后一步一定是把某个连续区间的左半与右半两堆并起来。于是问题天然带上了区间的结构——这正是区间 DP 的入口。

定状态。设 $dp[l][r]$ 表示：把第 $l$ 堆到第 $r$ 堆这段连续区间合并成一堆所需的最小代价。 要把 $[l,r]$ 合成一堆，最后一次合并必然是把某个分割点 $k$ 左边的 $[l,k]$（已合成一堆）与右边的 $[k+1,r]$（也已合成一堆）并起来。

这最后一并的代价是多少？两堆分别是 $[l,k]$ 和 $[k+1,r]$ 的全部石子，加起来恰好是整段区间的石子总和 $\mathrm{sum}(l,r)$——与 $k$ 断在哪里无关。 所以在分割点 $k$ 处断开的总代价是 $dp[l][k]+dp[k+1][r]+\mathrm{sum}(l,r)$。究竟断在哪个 $k$ 最好？把每个 $k$ 都试一遍，取最小：

边界：$dp[l][l]=0$（单独一堆无需合并）。答案：$dp[1][n]$。 区间和用前缀和 $\mathrm{sum}(l,r)=pre[r]-pre[l-1]$ 一步取到，不必每次重扫。

这里藏着区间 DP 与线性 DP 的关键分野：$dp[l][r]$ 依赖的是比它更短的子区间（$[l,k]$ 与 $[k+1,r]$ 长度都 $<r-l+1$）。所以递推不能按 $l$ 或 $r$ 顺序走，必须按区间长度由短到长——短的先算好，长的才有得引用。

用开头的例子（石子 $a=[7,6,5,4]$，下标 $1..4$）走几步。前缀和 $pre=[0,7,13,18,22]$，重点盯住长度由短到长：

区间 DP 的表是个上三角（只有 $l\le r$ 才是合法区间，下三角空着）。转移 $dp[l][r]$ 要用 $dp[l][k]$ 与 $dp[k+1][r]$，这两者的区间长度都比 $[l,r]$ 短。 所以只要先把所有短区间算完，长区间需要的子区间就一定都已就绪——这就是「外层枚举长度 $\mathrm{len}=2\ldots n$，内层枚举左端点 $l$」的由来。

数一数计算量：区间长度、左端点合起来约 $O(n^2)$ 个区间，每个区间还要枚举分割点 $k$（$O(n)$ 个），于是总复杂度 $O(n^3)$。 对石子合并的常见数据范围（$n\le$ 几百）绰绰有余。三层循环、外层是长度——这是几乎所有区间 DP 的通用骨架，记死它：

for 长度 len = 2 … n:          // ★外层枚举区间长度，由短到长
  for 左端点 l = 1 … n-len+1:
    r = l + len - 1
    for 分割点 k = l … r-1:
      dp[l][r] = min( dp[l][r], dp[l][k] + dp[k+1][r] + sum(l,r) )

石子合并的经典题（P1880）常常同时问最小与最大合并代价。好消息是：状态、转移骨架一字不改——只把那个 $\min$ 换成 $\max$，就从「最省」翻成「最费」：

两问共用同一套三层循环，用两张表 $f$（最小）、$g$（最大）并行填即可。下面把二者并排跑给你看：左边求最小、右边求最大。默认还是 $a=[7,6,5,4]$——最小 $44$、最大 $53$。改改石子数，看两个答案与各自选中的分割点如何分道扬镳。