大庆市网站建设_网站建设公司_定制开发_seo优化

经典问题描述：

有 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]; }