题面：
设有 \(N\) 堆石子排成一排，其编号为 \(1,2,3,…,N\)，现在要将这 \(N\) 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。请找出一种合理的方法，使总的代价最小，输出最小代价。
原题链接：282. 石子合并 - AcWing
乍一看上去很像哈夫曼树，但并不是，因为只能合并相邻的两堆。
必须相邻也成为了该题的关键，即最后一次合并的一定是连续的两堆。
区间DP
- 状态表示：所有将 \([i,j]\) 合并为一堆的方案集合，属性为最小值 \(min\) 。
- 状态计算：
- 分界点 \(k\) 的选择：在 \(i\) 到 \(j\) 区间内可以取 \(i,i+1,i+2,...j-1\)；
- 状态转移方程：\(f[i][j]=min(f[i][j],f[i][k],f[k+1][j]+s[j]-s[i-1])\)
- 区间DP常用模版[1]：长度+左端点
- 第一维通常是枚举区间长度，并且一般 \(len = 1\) 时进行初始化，枚举从 \(len = 2\) 开始；
- 第二维枚举起点 \(i\) （右端点 \(j\) 自动获得，\(j = i + len - 1\)）
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n;
int s[N]; //前缀和
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
//枚举区间长度len，若len=1，则不需要付出合并代价
for (int len = 2; len <= n; len++) {
//枚举起点i，从i开始的len长度区间不能超过n
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1; //终点j
f[i][j] = 1e8;
//枚举分界点k，范围为[i,j-1]
for (int k = i; k < j; k++)
//s[j]-s[i-1] 代表合并[i,k] [k+1,j] 这两堆石子的代价
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
cout << f[1][n];
}