【题目来源】
AcWing：282. 石子合并 - AcWing题库
【题目描述】
设有 \(N\) 堆石子排成一排，其编号为 \(1,2,3,\dots,N\)。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 \(4\) 堆石子分别为 1 3 5 2， 我们可以先合并 \(1\)、\(2\) 堆，代价为 \(4\)，得到 4 5 2， 又合并 \(1\)、\(2\) 堆，代价为 \(9\)，得到 9 2 ，再合并得到 \(11\)，总代价为 \(4+9+11=24\)；
如果第二步是先合并 \(2\)、\(3\) 堆，则代价为 \(7\)，得到 4 7，最后一次合并代价为 \(11\)，总代价为 \(4+7+11=22\)。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
【输入】
第一行一个数 \(N\) 表示石子的堆数 \(N\)。
第二行 \(N\) 个数，表示每堆石子的质量(均不超过 \(1000\))。
【输出】
输出一个整数，表示最小代价。
【输入样例】
4
1 3 5 2
【输出样例】
22
【算法标签】
《AcWing 282 石子合并》 #动态规划# #区间DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 305; // 定义常量N，表示数组的最大长度
int n; // 表示数组的长度
int a[N], s[N]; // a数组存储输入的数列，s数组存储前缀和
int f[N][N]; // f[i][j]表示将区间[i, j]合并的最小代价int main()
{cin >> n; // 输入数组的长度for (int i=1; i<=n; i++) {cin >> a[i]; // 输入数组的每个元素s[i] = s[i-1] + a[i]; // 计算前缀和，s[i]表示a[1]到a[i]的和}// 动态规划求解最小合并代价for (int len=2; len<=n; len++) { // len表示当前考虑的区间长度，从2开始for (int i=1; i+len-1<=n; i++) { // i表示区间的起点int j = i+len-1; // j表示区间的终点f[i][j] = 1e8; // 初始化为一个很大的数，表示初始状态为无穷大for (int k=i; k<j; k++) { // k表示在区间[i, j]中的分割点// 状态转移方程：f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])// f[i][k]表示区间[i, k]的最小合并代价// f[k+1][j]表示区间[k+1, j]的最小合并代价// s[j] - s[i-1]表示合并区间[i, j]的代价，即a[i]到a[j]的和f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);}}}cout << f[1][n] << endl; // 输出将整个区间[1, n]合并的最小代价return 0;
}
【运行结果】
4
1 3 5 2
22