🪨

区间 DP：合并石子

一排石子，每次只能把相邻两堆合成一堆（花费 = 两堆之和），合成一堆为止——怎么合并总花费最小？状态从「一格」变成「一段区间 [i, j]」：dp[i][j] = 把第 i 到第 j 堆合成一堆的最小花费。

💡 打个比方

想象操场边一排沙堆，老师规定：每次只能把紧挨着的两堆沙铲到一起，铲一次花费 = 两堆沙子总重；最后全部合成一堆，谁的办法总花费最少？贪心（每次合最小的两堆）不一定对——「现在花得少」可能让「后面花得多」。DP 的办法：给每一段连续的石子都算一个答案：dp[i][j] = 「把第 i 堆到第 j 堆合成一堆」的最小花费。怎么推？最后一步一定是「把左边一段 [i, k] 和右边一段 [k+1, j] 各合成一堆后，再合成一次」——所以 dp[i][j] = 对所有分界点 k 取 min(dp[i][k] + dp[k+1][j]) + sum(i, j)（sum 是这一段石子的总重，最后那次合并的花费）。基础：一段只有一堆时 dp[i][i] = 0（不用合）。填表顺序也变了：不能再「按行」填，而要按区间长度从小到大填（长度 2 → 3 → … → n），因为 dp[i][j] 要用到更短的区间的结果。

术语：区间 DP（状态是「一段连续区间 [i,j]」的 DP）；分界点 k（把 [i,j] 拆成 [i,k] 和 [k+1,j]，枚举所有拆法取最优）；区间长度优先（按 len = j-i+1 从小到大填表）；前缀和 sum(i,j)（一段的总重，O(1) 查询）。

🖼️ 大图看明白

合并石子：每次合并相邻两堆，花费 = 两堆之和（石子 4 2 1 3） 堆 1 堆 2 堆 3 堆 4 4 2 1 3 dp[1][2] = 6 dp[2][3] = 3 dp[3][4] = 4 dp[1][3] = 10 dp[2][4] = 9 dp[1][4] = 19 ← 答案（长度 4） 填表顺序：按区间长度 len = 2 → 3 → 4（短的先填） dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i, j) k 取 i ~ j-1 的所有分界点 sum(i, j) = 这段石子的总重 （最后那次合并的花费） 边界：dp[i][i] = 0（一堆不用合） 答案 = dp[1][n]（整段合成一堆） 为什么贪心不一定对？ 「先合最小的」可能让大堆 反复被合、花费重复计入—— 要枚举所有合并顺序（用 DP）

🧩 子任务 1：什么叫「合并石子」——手试几种合并顺序

🎯 小目标：理解规则（每次只能合并相邻两堆，花费 = 两堆之和，直到剩一堆），并能手算几种合并顺序的总花费（例：石子 4 2 1 3）。
// 石子：堆1 = 4，堆2 = 2，堆3 = 1，堆4 = 3（总重 10）
// 顺序 A：先合最左两堆
[4, 2, 1, 3] → 合 4+2 = 6（花费 6）→ [6, 1, 3]
[6, 1, 3] → 合 1+3 = 4（花费 4）→ [6, 4]
[6, 4] → 合 6+4 = 10（花费 10）→ [10]
总花费 = 6 + 4 + 10 = 20

// 顺序 B：先合中间两堆
[4, 2, 1, 3] → 合 2+1 = 3（花费 3）→ [4, 3, 3]
[4, 3, 3] → 合 3+3 = 6（花费 6）→ [4, 6]
[4, 6] → 合 4+6 = 10（花费 10）→ [10]
总花费 = 3 + 6 + 10 = 19

// 顺序 C：先合中间两堆，再合左边
[4, 2, 1, 3] → 合 2+1 = 3（花费 3）→ [4, 3, 3]
[4, 3, 3] → 合 4+3 = 7（花费 7）→ [7, 3]
[7, 3] → 合 7+3 = 10（花费 10）→ [10]
总花费 = 3 + 7 + 10 = 20
✅ 小检查：① 为什么顺序 B（19）比顺序 A（20）总花费更少？② 3 堆 a、b、c 只有 2 种合并顺序，两种的总花费分别是多少？③ 4 堆一共有几种不同的「合并方案」（先合谁再合谁）？
看看答案 ① 每种顺序的最后一步都必花 10（全部石子的总重），差别在早先几步：顺序 A 前两步花了 6 和 4，顺序 B 前两步花 3 和 6——先合小堆，合出来的堆还比较小，后面重复加的次数就少。 ② 先合 a+b：(a+b) + (a+b+c)；先合 b+c：(b+c) + (a+b+c)。 ③ 5 种（可以逐个枚举：第 1 步有 3 个相邻对可选，第 2 步有 2 个可选，其中「先合左对再合右对」和「先合右对再合左对」是同一方案）。5 种方案的总花费分别是 23、20、20、19、20，最小 = 19（就是顺序 B）。
⚠️ 易错：别以为「每次先合最小的两堆」一定最优——那是贪心的想法。本例恰好贪心（先合 2,1）就是最优；但换成石子 3 1 2 1 3，「总合最小的相邻两堆」要 24，巧妙顺序只要 23。想保证最优，得把每种拆法都试一遍（DP 的活）。

🧩 子任务 2：状态 + 转移——dp[i][j] 为什么成立

🎯 小目标：记住三件套——状态 dp[i][j]（把第 i 到第 j 堆合成一堆的最小花费）、转移（对所有分界点 k 取 min(dp[i][k]+dp[k+1][j])，再 + sum(i,j)）、填表顺序（按区间长度 len 从 2 到 n）。
// 状态定义：dp[i][j] = 把第 i 堆 ~ 第 j 堆合成一堆的最小花费
// 边界：一堆不用合，dp[i][i] = 0

// 转移怎么推（关键）：把 [i, j] 合成一堆，「最后」那一次合并
// 一定是把某个 k 左边的 [i, k] 合成一堆、右边的 [k+1, j] 合成一堆，
// 再把这两堆合成一次（花费 = 这一段石子总重 sum(i, j)）。
// 最优的最后一个分界点 k 不知道 → 枚举所有 k，取最小：
dp[i][j] = min( dp[i][k] + dp[k+1][j] )，k 取 i, i+1, ..., j-1
          + sum(i, j)

// 填表顺序：按区间长度 len 从小到大
//   len = 2：dp[1][2], dp[2][3], dp[3][4]（只用 dp[i][i] = 0）
//   len = 3：dp[1][3], dp[2][4]（用 len = 2 的结果）
//   len = 4：dp[1][4]（用 len = 2、3 的结果）
// 为什么：dp[i][j] 要用更短的区间 [i,k]、[k+1,j]，短的必须先填好。
// 答案 = dp[1][n]（整段合成一堆）。
✅ 小检查：① 「最后一次合并」的花费为什么恰好是 sum(i, j)？② k 能不能取到 j？为什么只到 j-1？③ 如果像 LIS/LCS 那样按行填，哪个格会「用到还没填的值」？
看看答案 ① 最后一次合并时，左边已合成一堆、右边已合成一堆，两堆石子合起来正好是 [i, j] 这段全部石子，花费 = 总重 sum(i, j)。 ② 若 k = j，右边 [k+1, j] = [j+1, j] 是「空区间」，左边 [i, k] 就是整个 [i, j] 自己——转移就变成用 dp[i][j] 算 dp[i][j] 了。所以 k 只取 i ~ j-1，保证两部分都比原区间短。 ③ 比如算 dp[1][3]（第 1 行）要 dp[2][3]（第 2 行）——按行填时还在第 1 行，第 2 行还没填。按区间长度填就没这问题。
⚠️ 易错：转移里 min 的括号别漏——先对所有 k 取 min，再 + sum(i, j)（sum 只加一次）。写成 dp[i][k] + dp[k+1][j] + sum 每个 k 都加，答案会偏大。

🧩 子任务 3：手填 4 2 1 3 的整张 dp 表 + 倒推最优合并顺序

🎯 小目标：按 len = 2 → 3 → 4 填完 dp 表（答案 dp[1][4] = 19），并倒推出最优方案的第一步。
// 按区间长度填表（对角线 len = 1 全是 0，不写）
// len = 2（k 只有 i，两边都是单堆，min = 0）：
dp[1][2] = 0 + (4+2) = 6
dp[2][3] = 0 + (2+1) = 3
dp[3][4] = 0 + (1+3) = 4
// len = 3（k 取 2 个值，取小的）：
dp[1][3] = min(0+3, 6+0) + 7 = 3 + 7 = 10
dp[2][4] = min(0+4, 3+0) + 6 = 3 + 6 = 9
// len = 4（k 取 3 个值，取小的）：
dp[1][4] = min(0+9, 6+4, 10+0) + 10 = 9 + 10 = 19  ← 答案！

// 倒推策略（从 dp[1][4] 出发，每步看「哪个 k 最小」）：
dp[1][4]：k = 1 最小（9）→ 最后一次合并 = [1] + [2..4]
  dp[2][4]：k = 3 最小（3）→ [2,4] 内最后合并 = [2,3] + [4]
    dp[2][3]：k = 2 最小（0）→ [2,3] 内最后合并 = [2] + [3]
// 把「最后合并」反过来排，就是执行顺序——最优方案第 1 步 = 合并堆 2 和堆 3！
第 1 步：合并堆 2、3 → 花费 2+1 = 3，石子变 [4, 3, 3]
第 2 步：合并（刚合的堆）和堆 4 → 花费 3+3 = 6，石子变 [4, 6]
第 3 步：全部合并 → 花费 4+6 = 10，石子变 [10]
总花费 = 3 + 6 + 10 = 19 ✓（和 dp[1][4] 对上）
✅ 小检查：① 你算出的 dp[1][4] 是多少？和子任务 1 里 5 种方案的最小值一致吗？② 倒推时「哪个 k 最小」具体指什么最小？③ 为什么倒推出的合并步骤要「反过来」才是执行顺序？
看看答案 ① dp[1][4] = 19，和 5 种方案的最小值（19）一致——DP 就是「把每种方案系统地试一遍、取最好」，只是不重复计算。 ② 每一步取使 dp[i][k] + dp[k+1][j] 最小的那个 k：dp[1][4] 取 k=1（9），dp[2][4] 取 k=3（3），dp[2][3] 取 k=2（0）。这个 k 是该区间「最后合并」的分界点。 ③ dp 记录的是「最后一次怎么合」，时间上它发生在最后；倒推时先找到的其实是最后一步，反过来排才是从第 1 步开始的执行顺序（先合并堆 2、3）。
⚠️ 易错：填表时别按行填（先填完第 1 行再填第 2 行）——口诀「长度优先」：len 循环在外、i 在内、j = i + len - 1。另外转移的 min 必须枚举 i ~ j-1 的所有 k，漏一个拆法答案就可能偏大。

🧩 子任务 4：代码要点——三重循环 len / i / k + 前缀和

🎯 小目标：记住三重循环结构（len 在外、i 在中、k 在内）、前缀和 sum(i,j) = pre[j] - pre[i-1]，以及 best 的初始化。
// 要点 1：前缀和——sum(i, j) = pre[j] - pre[i-1]，O(1) 查出一段总重
pre[0] = 0;
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];

// 要点 2：三重循环——len 在外（2~n）、i 在中（区间起点）、k 在内（枚举分界点）
for (int len = 2; len <= n; len++)            // 区间长度从小到大
  for (int i = 1; i + len - 1 <= n; i++) {   // 起点 i，保证 j 不越界
    int j = i + len - 1;
    int best = 1e9;
    for (int k = i; k <= j - 1; k++)         // 枚举所有分界点
      best = min(best, dp[i][k] + dp[k+1][j]);
    dp[i][j] = best + (pre[j] - pre[i-1]);   // + 最后一次合并的花费
  }

// 要点 3：答案 = dp[1][n]（整段合成一堆）
✅ 小检查：① i 循环为什么写成 i + len - 1 <= n？② 若每次用循环现算 sum(i,j)，总复杂度变成几阶？③ n = 1000 时三重循环大约跑多少次（量级）？
看看答案 ① j = i + len - 1 不能超过 n，这个条件保证区间 [i, j] 落在 1 ~ n 里（起点 i 最远到 n - len + 1）。 ② 每次现算 sum 等于多套一层循环，总复杂度 O(n⁴)；前缀和让查询 O(1)，总复杂度保持 O(n³)。 ③ 总循环次数约 n³/6，n = 1000 时约 1.7 亿次——1 秒内擦线，所以 sum 必须用前缀和 O(1) 查，别现算。
⚠️ 易错：best 的初值。要初始成一个大数（如 1e9）再 min——若初始成 0，而花费都是正数，结果永远是 0 + sum（偏小）。这是「求最小值」循环的固定套路：先给一个「肯定比答案大」的初值。

💻 完整代码：合并石子（区间 DP + 前缀和）

// 题目：n 堆石子排成一排（n ≤ 300），每次只能把相邻两堆合成一堆，
// 花费 = 两堆之和。求合成一堆的总花费最小值。
// 输入：第 1 行 n；第 2 行 n 个整数（每堆石子数）。
#include <iostream>
#include <algorithm>
using namespace std;

int a[305], pre[305], dp[305][305];

int main() {
    int n;
    cin >> n;
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];        // 前缀和：pre[j] - pre[i-1] = sum(i, j)
    }

    // 三重循环：len 在外、i 在中、k 在内（按区间长度从小到大填表）
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            int best = 1e9;
            for (int k = i; k <= j - 1; k++)
                best = min(best, dp[i][k] + dp[k+1][j]);
            dp[i][j] = best + (pre[j] - pre[i-1]);   // + 最后一次合并
        }

    cout << dp[1][n] << endl;         // 答案：整段合成一堆
    return 0;
}

// 样例：输入 4 / 4 2 1 3 → 输出 19
// 延伸：若还要输出「合并顺序」，需另开数组 kbest[i][j] 记录每个 dp[i][j]
// 取到最小值时的 k，再从 dp[1][n] 倒推（子任务 3 的手推就是这个过程）。

✋ 你来试试

第 1 题：3 堆石子 1 1 1，最小总花费 = ？ 5——只有 2 种顺序，但总花费一样：先合任意两堆（花费 2），再合最后两堆（花费 3），2 + 3 = 5。dp 表：dp[1][2] = dp[2][3] = 2，dp[1][3] = min(0+2, 2+0) + 3 = 5。
第 2 题：只有 2 堆 a、b，最小总花费 = ？ a + b——只有一种合法，一次合并。对应 dp[i][i+1] = a + b（min 部分 = 0，只加 sum）。
第 3 题：5 堆全是 1（1 1 1 1 1），最小总花费 = ？ 12——len2 = 2，len3 = min(0+2, 2+0)+3 = 5，len4 = min(0+5, 2+2, 5+0)+4 = 8，dp[1][5] = min(0+8, 2+5, 5+2, 8+0)+5 = 7 + 5 = 12。手推验证：(1+1)=2，(1+1)=2，2+1=3，2+3=5，共 2+2+3+5 = 12 ✓。
第 4 题（加餐）：4 2 1 3 的最优方案，第 1 步合并哪两堆？第 1 步花费多少？ 合并堆 2 和堆 3（2+1 = 3）。倒推链：dp[1][4] 取 k=1 → dp[2][4] 取 k=3 → dp[2][3] 取 k=2，最里层就是「堆 2 + 堆 3」。总花费 3 + 6 + 10 = 19。
🎯 一句话记住：区间 DP「合并石子」——dp[i][j] = 一段合成一堆的最小花费；转移 = 枚举所有分界点 k 取 min(dp[i][k]+dp[k+1][j])，再 + sum(i,j)；按区间长度 len 从 2 填到 n，dp[i][i] = 0；答案 = dp[1][n]。
← 上一课：最长公共子序列 LCS 下一课：滚动数组 →