石头子合并—区间DP详解
f[i,j]的意思就是所有将第i堆石子到第j堆石子合并成一堆石子的合并方式。
那么如何进行计算呢???
首先明确,最后一步一定是将两堆合并成一堆,那么从后往前怎么分类呢?
所以我们以最后一次的分界线来分配,想象出来一根绳子,以单位长度划分,那么便有以下这么多种划分方式
从符号上看,左边就是i—>k,右边是k+1—>j
由此可得dp公式=左边的最小代价f[i,k]加上右边的最小代价f[i+1,j]加上最后一步的最小代价s[j]-s[i-1]
最后一步的最小代价由前缀合处理(相当于一个数列)
算法1
两层循环,第一层循环长度,第二层在长度一定的过程中寻找最短代价
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=310;
const int INF=1e9;
int n;
int s[N];
int f[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&s[i]);
for(int i=1;i<=n;i++)s[i]+=s[i-1];
//上面的都是基本初始化op
for(int len=2;len<=n;len++)//len就是题解中的j也就是长度
for(int i=1;i+len-1<=n;i++)
{
int l=i,r=i+len-1;
//if(len==1)边界情况,此时区间为0不需要代价
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]);
}
printf("%d",f[1][n]);
return 0;
}