思路：
（1）f[l][r]表示l~r之间合并的最小代价。
（2）将l~r拆成l~k,k+1~r两份分别最优合并，再把两份合并，对于每个l,r通过枚举所有可能k探寻最优。
（3）最终目标是f[1][n]，注意到长区间是由短区间递推出来的，所以由小到大枚举区间长度，再枚举起点，此时l = 起点，r = 起点 +len - 1;此时再枚举k，注意到k+1<=r所以k < r;文章来源：https://www.toymoban.com/news/detail-685101.html
（4）初始化：由于len = 1时，合并代价为0，故无需初始化,len从2开始枚举即可，由于l~r要实现更新，所以枚举k前要先将f[l][r]初始化为无穷大，方便被拆分时更新。文章来源地址https://www.toymoban.com/news/detail-685101.html
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 310;
int a[N],f[N][N],s[N];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> a[i];
for(int i = 1;i <= n;i ++)
s[i] = s[i - 1] + a[i];
for(int len = 2;len <= n ;len ++)
{
for(int l = 1;l +len - 1 <= n;l ++)
{
int r = l + len - 1;
f[l][r] = 0x3f3f3f3f;
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] << endl;
return 0;
}到了这里，关于石子合并（区间dp)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
