石子合并

**(区间DP) **

0.思路

关键点：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

如何分类：最后一次分界线的位置来分类，分成k类之后，每一类取最小代价
步骤：
1.枚举[l,r]区间的长度
2.对于每个长度的区间
枚举起点———— 合并开始的位置

for(int i = 1;i + len - 1 <= n;i ++)

对应的就有终点———— 合并结束的位置

j = i + len -1;

3.枚举分界点 k
for(int k = i ;k < j;k++)

!k不能等于j

1.说明右端至少有1堆
2.在下面进行说明

1.状态定义

f[i][j] : 将 i到j 这一段石子合并成一堆的方案的集合

2.状态计算

** f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);**

从这里f[k+1][j]看出k!=j，如果k=j的话 k+1>j就会产生矛盾

3.初始化

1.区间长度为1的时候力贡献为0
2.由于是取最小值，将f[i][j]=INF;

4.前缀和

for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+a[i];  //维护区间和
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 310;

int n;
int a[N],s[N]; //前缀和 
//从第i堆到第j堆合并的代价 
int f[N][N]; 

int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];   //计算前缀和 
	}
	
	for(int len=2;len<=n;len++) //枚举区间长度  
	 for(int i=1; i+len-1<=n;i++){  //枚举起点 
	 	int l=i,r=i+len-1;   //l为左端点，r为右端点  
	 	//枚举每个分界点k 
	 	 f[l][r]=1e9;   //因为取得是最小值所以初始化最大值 
	     for(int k = l;k < r;k ++) //k 的范围 (1,j-1) -j-1是因为右边至少有一堆  
	     f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);  //s[r]-s[l-1] 是[l,r]区间的总价值
	 } 
	 cout<<f[1][n];
	 return 0;
}