题目描述

设有 $N$ 堆石子排成一排，其编号为 $1，2，3，…，N。$

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

分析

状态表示：f[i][j]表示将i - j这一堆石子合并的所有方案的集合
属性：Min

状态计算：
将集合划分成：
k ∈[l,r)
将石子划分成$i 到 k$ 和 $k 到 1-j$两堆进行合并
状态转移方程为:
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));

区间DP

通常对于区间DP问题，我们都采用先枚举区间长度，再枚举区间左端点的方式
并且一般 len = 1 时用来初始化，枚举从 len = 2 开始
右端点可以通过r = l + len - 1 来计算,模板如下：

for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}

模板参考自白马金羁侠少年

C++ Code

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int q[N],s[N],f[N][N]; // f[i][j] 代表将i - j这一堆石子合并的方案的集合
int n;

int main()
{
    cin >> n;
    // 预处理前缀和
    for(int i = 1; i <= n ; ++i){
        cin >> q[i];
        s[i] = s[i - 1] + q[i];
    }

    // 区间dp： 先枚举左端点，再枚举区间长度
    for(int len = 2; len <= n; ++len){
        for(int l = 1; l + len - 1 <= n ; ++l){
            int r = l + len - 1;
            f[l][r] = 1e8;
            for(int k = l; k < r; ++k){
                f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}