石子合并

最经典的区间dp题。

思路

让我们先看最简单的，两堆石子合并。费用自然只能是两组石子之和。

那么三堆呢？我们可以先合并前两个或后两个，无论怎么合并，最后一步费用一定是三组石子之和。

四堆中，我们从左往右有三种方法合并，但每一种最后一步费用一定是整段的和。

那么让我们推广到n堆石子合并，合并的方法有n-1种，而每一种方法都可以表示为将某堆以及该堆左边所有石子合并，再把右边所有石子一起合并,

所以我们不妨在区间中枚举一个断点，以此求区间最值。因为每一种方法都可能是最小的，我们为了求长度为n的区间，需要求出长度从2到n-1所有区间的长度。

于是聪明的你一定已经想到了状态转移方程：

让我们枚举一个断点i。

$\red{dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+整段的和)}$

好了，结束。

代码

int Dp[500][500];
int a[500], Sum[500];
int n;

int main()
{
    scanf("%d", &n);
    memset(dp,0x3f,sizeof(dp)); //为了求最小值
    for (int i = 1;i <= n;i++)
    {
        dp[i][i]=0; //合并一堆石头不需费用
        scanf("%d", &Sum[i]), Sum[i] += Sum[i-1];// 每一步都需要区间求和，不妨用前缀和
    }
    for (int len = 2;len <= n;len++) //区间长度
        for (int l = 1,r=len;r <= n;l++,r++) // 左右端点
            for (int k = l;k < r;k++)//枚举断点
                Dp[l][r] = min(Dp[l][r], Dp[l][k]+Dp[k+1][r]+Sum[r]-Sum[l-1]);
    printf("%d\n", Dp[1][n]);
}