设石子总数为n
所求问题：1到n这些石子合并最少需要多少代价
由于石子合并的顺序可以任意，我们将石子分为两个部分
子问题：1到k这堆石子合并，k+1到n这堆石子合并，再把两堆石子合并，需要多少代价（1<=k<=n）

那么便可以得到状态转移方程 dp[i][j]=min(dp[i][k]+dp[k+1][j]+……)
i到j这些石子合并，代价不仅仅是分开的两堆内部合并的代价，还有两堆石子相互合并的所带来的代价消耗，可得出省略号中的答案为a[i]+a[i+1]+……+a[j]
为了加快效率，我们设立一个sum数组来记录前缀和，那么可得到完整的状态转移方程：

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

需要注意的是，由于dp求最小值，需要将dp预处理为无穷大，以下便是本题的AC代码：

#include <bits/stdc++.h>
using namespace std;
int a[1050];
int sum[1050];
int dp[1050][1050];
int main()
{
    memset(dp,0x3f,sizeof(dp));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=a[i]+sum[i-1];
    }
    for(int j=1;j<=n;j++)
    {
        for(int i=j;i>=1;i--)
        {
            if(i==j) dp[i][j]=0;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    }
    printf("%d\n",dp[1][n]);
}