区间DP

石子合并

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

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

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

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

状态表示

$f[i][j]$所有将第$i$堆石子到第$j$堆石子合并成一堆石子的合并方式

状态计算

$f[l][r]=Min(f[l][r],f[l][k]+f[k+1][r]＋s[r]-s[l-1])$ 合并以$k$为分界的左右区间费用的最小值加上合并当前区间的费用

const int N = 305;
int s[N];
int f[N][N];

int main() {
   
	int n;cin >> n;
	for (int i = 1;i <= n;++i)cin >> s[i];
	for (int i = 1; i <= n;++i)s[i] += s[i - 1];

	for(int len = 2; len <= n ;++len){
   //区间长度
		for (int i = 1;i + len - 1 <= n;++i) {
   //起点
			int l = i, r = i + len - 1;//区间端点
			f[l][r] = INF;
			for (int k = l;k < r;++k) {
   //枚举分界线
				f[l][r] = min(f[l][r], f[l][k]+ f[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}
	cout << f[1][n];
	return 0;
}