经典问题描述：
有 n 堆石子排成一排，第 i 堆有 ai 个石子。
每次只能合并相邻的两堆，合并代价等于这两堆石子的总数。
合并后形成一堆新石子。
问：把所有石子合并成一堆的最小总代价。
输入
3(n的大小)
8 5 8
输出
34
解释：首先合并8-5成13，代价是13. 合并后石子为13 8.然后合并13-8，代价是21.所以总代价为34
贪心or动态规划
在石子合并里，最自然的贪心直觉只有这一种：
每一步都合并当前代价最小的相邻两堆
也就是：每次找 a[i] + a[i+1] 最小的一对，先合它
这个策略非常“像 Huffman”，所以特别容易误入。
⚠️ 问题就出在：
石子合并中，一次合并的结果，会被“反复收费”
所以当前的最小代码，并不是全局的最小代价。这就是贪心失效的根本原因
贪心反例
石子堆： 4 3 3 4
贪心做法（每次合最小相邻对）
1️⃣ 合并中间的3 + 3 = 6
代价 = 6
现在变成：4 6 4
2️⃣ 合并4 + 6 = 10（或 6+4）
代价 = 10
现在变成：10 4
3️⃣ 合并10 + 4 = 14
代价 = 14
📌 总代价：6 + 10 + 14 = 30
最优做法（非贪心）
1️⃣ 先合左边4 + 3 = 7
代价 = 7
7 3 4
2️⃣ 再合右边3 + 4 = 7
代价 = 7
7 7
3️⃣ 最后合并7 + 7 = 14
代价 = 14
📌 总代价：7 + 7 + 14 = 28
这是一个「区间 DP」问题
记住一句判断口诀：
“对象是连续区间，决策是选断点，代价和区间整体有关”
→ 基本就是区间 DP
我们逐条对照石子合并：
状态的本质是什么？
最终不是关心“某一步怎么合”，
而是关心：
某一段连续石子合并成一堆，最少要花多少钱
这句话本身就已经是一个区间：[l ........ r]
所以状态一定是：dp[l][r] = 把第 l 堆到第 r 堆合并成一堆的最小代价
⚠️ 注意：
不是过程
是“已经合并完成”的最优结果
状态转移是怎么发生的
不管你前面怎么合：
最后一步
一定是把某两堆「已经合并好的大堆」合成一堆
而这两堆必然形如：
[l .... k] + [k+1 .... r][l..k]和[k+1..r]各自已经合成一堆；合并它们的代价 =区间总石子数
设前缀和：sum[i] = a1 + a2 + ... + ai
那么：cost(l, r) = sum[r] - sum[l-1]
所以状态转移就只能是：
dp[l][r] = min over k∈[l, r-1] ( dp[l][k] + dp[k+1][r] + cost(l, r) )边界条件
一个堆需要合并吗？
dp[i][i] = 0不需要任何代价
C++代码实现
int sum(int prefix[], int l, int r) { return prefix[r] - prefix[l - 1]; } int main() { int n; cin >> n; int a[107], prefix[107] = { 0 }; //我这里下标是从1开始的 for (int i = 1; i <= n; i++) { cin >> a[i]; } //prefix[i]是从[1,i]的和 for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + a[i]; } //dp表示把区间 [l, r] 合并成一堆的最小代价 long long dp[107][107]; //单根不用合并 for (int i = 1; i <= n; i++) dp[i][i] = 0; //枚举合并区间长度 for (int len = 2; len <= n; len++) { //枚举开始位置 for (int l = 1; l + len - 1 <= n; l++) { //区间是[l,l+len-1],长度就是len int r = l + len - 1; dp[l][r] = LLONG_MAX; //所谓合并，可以这么理解 //如果[l,k]和[k+1,r]已经合并完了，那么再合并的代价就是sum(l,k)+sum(k+1,r)即sum(l,r) //然后[l,k]和[k+1,r]也有合并的代价，所以[l,k]和[k+1,r]的合并代价就是dp[l][k]+dp[k+1][r]+sum(l,r) //我们枚举所有k属于[l,r)，这样就能找到dp[l][r]的最小合并代价 for (int k = l; k < r; k++) { dp[l][r] = fmin(dp[l][r], dp[l][k]+dp[k+1][r]+sum(prefix,l,r)); } } } cout << dp[1][n]; }
