-
2、类似Huffman树的石子合并
- Huffman树是所有任意两堆石子可以任意合并，但是该DP问题只能合并相邻的两堆，所以用区间DP
- 按照区间长度遍历，先遍历两堆的最小值显然是所有相邻两堆相加，遍历三堆及以上时就要考虑那种更优，通过从l~r-1划线的方式找最优的解，前提是前面的状态已经被计算过
- 像1 3 5
- 前面的状态f（1，2）=4，f（2，3）=8
- 所以在1~2划线f（1，3）=min（f（1，1）+f（2，3），f（1，2）+f（3，3））
- 同理最终状态f（1，n）就是最小值
- 代码
#include<iostream>
using namespace std;
const int N=310;
int f[N][N];
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) a[i]+=a[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]=2e9;
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1]);
}
}
cout<<f[1][n]<<endl;
return 0;
}