GESP 八级 · GESP202609 C++ 八级 第 3 题

有 4 堆石子，数量分别为 1、2、3、4。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（ ）。

看到这题先想区间 DP 框架：dp[i][j] 表示合并第 i 到 j 堆的最小代价，状态转移是枚举中间分割点 k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i..j))。因为石子数已排序，也可用贪心：每次合并相邻最小的两堆，本质是构建最优二叉合并树。

A 项 17 是贪心合并 1+2+3+4 的简单累加，忽略了每次合并后新堆会参与后续合并；C 项 20 是合并顺序不当（如先合 3+4 再合 1+2）产生的次优解；D 项 23 是把 4 当作独立堆最后再合并，代价最大。

1. 考纲定位

本题考查《GESP 八级》"动态规划与区间问题"模块。命题人卡住的是考生对"区间最优子结构"的直觉——多数人会直接贪心合并最小的两堆，却忽略合并后的新堆会参与后续合并，导致代价被低估。

2. 解题思维

DP 建模：设 dp[i][j] 为合并第 i 到 j 堆的最小代价。

• 基础情况：dp[i][i] = 0
• 转移：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i..j))，k 从 i 到 j-1

手工推演（石子数 1,2,3,4）：

• dp[1][2] = 1+2 = 3
• dp[2][3] = 2+3 = 5
• dp[3][4] = 3+4 = 7
• dp[1][3] = min(3+5, 3+0+6) = 9
• dp[2][4] = min(5+7, 5+0+9) = 14
• dp[1][4] = min(3+7+10, 9+0+10, 0+14+10) = 19

贪心验证：1+2=3 → 3+3=6 → 6+4=10，总代价 3+6+10 = 19。两种方法一致。