AcWing 282. 石子合并

题面：
设有 \(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];
}