题目描述

链接：https://ac.nowcoder.com/acm/problem/51170
来源：牛客网

题目思路

原问题：找到n堆石子合并的最小代价dp[1][n]
子问题：找到第i到j堆石子合并的最小代价dp[i][j]
第i到j堆石子合并的最小代价=第i到k堆石子合并的最小代价+第(k+1)到j堆石子合并的最小代价+第i到j堆石子数量和.
即一次合并的最小代价，不仅是其划分出的的这两堆石子在自身合并时带来的代价和，还要考虑这两堆石子自身的数量和。
设sun[i]代表从第1堆到第i堆石子数量之和，则有
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])

完整代码

#include <bits/stdc++.h>
using namespace std;
int a[310];
long long dp[310][310], sum[310];

int main()
{
    long long res = 0;
    int n;
    scanf("%d",&n);
    int i=1;
    while(i<=n)
    {
        scanf("%d",&a[i]);
        i++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            sum[i]+=a[j];
        }    
    }

    for(int i=n-1;i>0;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=i;k<j;k++)
            {
                if(dp[i][j] == 0)
                    dp[i][j] = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                else
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    printf("%d",dp[1][n]);
    return 0;
}