算法1

区间行型动态规划

区间Dp简述：就是用一个二维数组表示一个区间在此区间内进行操作

实现步骤

1.首先枚举选选区的长度len从2到n[2,n);

2.其次再枚举起点i从1到n-len+1;这样就可以计算出终点i+len-1;

3.最后枚举一下中转点k，从i到j-1（因为每一个合并的石子都至少有一堆）；

1.状态表示：f[i][j]表示从i到j这个区间内合并的最小价值；

2.状态转移：
<1>因为中转点k是枚举的所以把这一个区间分成了两部分；

如果把这两部分合并（计算出从起点到终点的石子堆的总和），加上经过中转点已经算出合并出了最小代价的区间的代价，就就可以直接和并了;

因为要计算出从起点到中点石子堆的总和所以可以用前缀和sum数组优化程序；

sum[r]-sum[l-1]就可以求出起点到终点的石子堆的总和；

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

最后输出f[1][n]，表示1为起点，n为终点合并的最小价值 就可以了；

时间复杂度O（n * n * n）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int f[1001][1001],s[1001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[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[i][r]=2e9;//不要忘了初始化，要不就没法打擂台了
            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;
}

题解如有不严谨之处请谅解，望大佬们指导；