区间DP：石子合并（弱化版）

区间DP是动态规划的一个重要分支，专门解决区间上的最优解问题。和之前学的线性DP不同，线性DP的状态是单个点（比如dp[i]表示到第i个位置的最优解），而区间DP的状态是一个连续的区间（比如dp[l][r]表示从第l个位置到第r个位置的最优解）。

一、问题分析

题目重述

有N堆石子排成一排，每堆有质量m[i]。每次只能合并相邻的两堆，合并代价是这两堆的质量之和。问把所有石子合并成一堆的最小总代价是多少？

为什么不能用贪心？

很多同学第一反应是贪心：每次合并质量最小的相邻两堆。但这个策略是错的，因为只能合并相邻的堆，贪心无法保证全局最优。

举个反例：6 4 4 6

• 贪心策略：先合并最小的相邻堆4和4（代价8），得到6 8 6；再合并6和8（代价14），得到14 6；最后合并（代价20）。总代价8+14+20=42。
• 正解：先合并左边两个相邻堆6和4（代价10），得到10 4 6；再合并4和6（代价10），得到10 10；最后合并（代价20）。总代价10+10+20=40。

贪心在这里得到了更差的结果，因为它只考虑了当前一步的最优，而没有考虑后续合并的代价。这就是为什么我们需要用动态规划来解决这个问题。

二、区间DP解题四步走

所有区间DP问题都遵循同一个解题框架，我们一步步来拆解。

第一步：定义状态

区间DP的状态定义非常固定：

dp[l][r] = 合并从第l堆到第r堆石子的最小总代价

这里的l是区间的左端点，r是区间的右端点。比如dp[1][4]就表示合并第1到第4堆石子的最小代价，也就是我们最终要求的答案。

第二步：推导状态转移方程

要合并l到r这一堆，最后一步一定是把这个大区间分成两个相邻的小区间，然后把这两个小区间合并成一个。

比如合并1到4，最后一步可能是：

• 合并1到1和2到4
• 合并1到2和3到4
• 合并1到3和4到4

我们需要在所有可能的分割点中，找到总代价最小的那个。

所以状态转移方程是：

dp[l][r] = min(dp[l][k] + dp[k+1][r]) + sum(l, r)

其中k是分割点，范围是l ≤ k < r。

为什么要加sum(l, r)？

sum(l, r)表示第l到第r堆石子的总质量。因为不管前面怎么合并，最后合并两个大区间的代价，一定是这两个大区间的总质量之和，也就是整个区间的总质量。

前缀和优化

为了快速计算sum(l, r)，我们可以预处理一个前缀和数组s：

• s[0] = 0
• s[i] = m[1] + m[2] + ... + m[i]

那么sum(l, r) = s[r] - s[l-1]，这样每次计算区间和只需要O(1)的时间。

第三步：确定初始值

当区间长度为1的时候（也就是l == r），只有一堆石子，不需要合并，所以代价为0：

dp[l][l] = 0 （对所有1 ≤ l ≤ n）

其他所有dp[l][r]（l < r）初始化为一个很大的数（比如1e9），表示一开始我们还不知道怎么合并这个区间。

第四步：确定计算顺序

这是区间DP最关键的一步，也是和线性DP最大的区别。

要计算长度为len的区间的最优解，必须先计算出所有长度小于len的区间的最优解。因为长区间是由两个短区间合并而来的。

所以我们的计算顺序是：

1. 先计算所有长度为2的区间（len=2）
2. 再计算所有长度为3的区间（len=3）
3. ...
4. 最后计算长度为n的区间（len=n），也就是最终答案

对应的代码结构是：

// 外层循环：枚举区间长度
for (int len = 2; len <= n; len++) {
    // 中层循环：枚举左端点
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1; // 右端点
        // 内层循环：枚举分割点k
        for (int k = l; k < r; k++) {
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r] - s[l-1]);
        }
    }
}

三、样例详细计算过程

我们用题目给出的样例来一步步计算，验证我们的思路是否正确。

样例输入：

4
2 5 3 1

第一步：预处理前缀和

s[0] = 0
s[1] = 2
s[2] = 2+5 = 7
s[3] = 7+3 = 10
s[4] = 10+1 = 11

第二步：初始化dp数组

所有dp[l][l] = 0，其他为INF。

第三步：按区间长度从小到大计算

1. 区间长度len=2

• l=1, r=2：k=1
  dp[1][2] = dp[1][1] + dp[2][2] + s[2]-s[0] = 0+0+7 = 7
• l=2, r=3：k=2
  dp[2][3] = 0+0 + (10-2) = 8
• l=3, r=4：k=3
  dp[3][4] = 0+0 + (11-7) = 4

2. 区间长度len=3

• l=1, r=3：k可以是1或2

  • k=1：dp[1][1] + dp[2][3] + 10 = 0+8+10 = 18
  • k=2：dp[1][2] + dp[3][3] + 10 = 7+0+10 = 17
    取最小值，dp[1][3] = 17

• l=2, r=4：k可以是2或3

  • k=2：dp[2][2] + dp[3][4] + 9 = 0+4+9 = 13
  • k=3：dp[2][3] + dp[4][4] + 9 = 8+0+9 = 17
    取最小值，dp[2][4] = 13

3. 区间长度len=4（最终答案）

• l=1, r=4：k可以是1,2,3

  • k=1：dp[1][1] + dp[2][4] + 11 = 0+13+11 = 24
  • k=2：dp[1][2] + dp[3][4] + 11 = 7+4+11 = 22
  • k=3：dp[1][3] + dp[4][4] + 11 = 17+0+11 = 28
    取最小值，dp[1][4] = 22

四、完整代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const int INF = 1e9;

int m[N]; // 每堆石子的质量
int s[N]; // 前缀和数组
int dp[N][N]; // dp[l][r]表示合并l到r的最小代价

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m[i];
        s[i] = s[i-1] + m[i]; // 预处理前缀和
    }
    
    // 初始化dp数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = INF;
        }
        dp[i][i] = 0; // 长度为1的区间代价为0
    }
    
    // 区间DP核心
    for (int len = 2; len <= n; len++) { // 枚举区间长度
        for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点
            int r = l + len - 1; // 右端点
            for (int k = l; k < r; k++) { // 枚举分割点
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r] - s[l-1]);
            }
        }
    }
    
    cout << dp[1][n] << endl;
    return 0;
}

五、区间DP共通性总结

所有区间DP问题都有以下几个共同点：

1. 状态定义固定：几乎都是dp[l][r]表示区间[l, r]的最优解
2. 转移方式固定：都是枚举中间分割点k，把大区间分成两个小区间，用小区间的最优解合并得到大区间的最优解
3. 计算顺序固定：必须按区间长度从小到大计算，因为长区间依赖于短区间
4. 常用前缀和优化：快速计算区间和，降低时间复杂度

这道题的时间复杂度是O(n³)，对于n≤300的数据来说完全足够。如果n更大（比如n≤1000），还可以用四边形不等式优化到O(n²)，但对于入门来说，掌握O(n³)的基础写法就足够了。