石子合并最大最小值(區間dp)

一條直線上擺放着一行共n堆的石子。現要将石子有序地合并成一堆。規定每次隻能選相鄰的兩堆合并成新的一堆，并将新的一堆石子數記為該次合并的得分。請編輯計算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int a[1515];
int dp[105][105];
int sum[105];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];//從1~i可得分;
        }
        memset(dp,0x3f3f3f3f,sizeof(dp));
        for(int i=1;i<=n;i++)dp[i][i]=0;//初始化
        for(int d=1;d<n;d++)//枚舉區間長度
        {
            for(int i=1;i<=n-d;i++);//i+d<=n
            {
                int j=i+d;//j是終點;
                for(int k=i;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
                dp[i][j]+=sum[j]-sum[i-1];//加上得分;
            }
        }
        printf("%d ",dp[1][n]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)dp[i][i]=0;
        for(int d=1;d<n;d++)
        {
            for(int i=1;i<=n-d;i++)
            {
                int j=i+d;
                for(int k=i;k<j;k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
                dp[i][j]+=sum[j]-sum[i-1];
            }
        }
        printf("%d\n",dp[1][n]);
    }
}