51nod1021 돌멩이 병합(구간dp)

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
int a[105],sum[105];
int dp[105][105];
const int INF=0x3f3f3f3f;
void init()
{
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));
    memset(a,0,sizeof(a));
}
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
       init();
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&a[i]);
           sum[i]=sum[i-1]+a[i];
       }
       for(int len=2;len<=n;len++)
       //   len  2   ，           len-1，  len         ，     i     ，   -1，  len    
       {
           for(int i=1;i+len-1<=n;i++)//i      
           {
               dp[i][i+len-1]=INF;//     min，       INF
               for(int k=i;k<=i+len-1;k++)//k        
               {
                   dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]+sum[i+len-1]-sum[i-1]);
               }
           }
       }
       printf("%d
",dp[1][n]);
   }
    return 0;
}

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int a[1005],sum[1005];
int dp[1005][1005];
int n;
const int INF=0x3f3f3f3f;
void init()
{
    memset(sum,0,sizeof(sum));
    memset(a,0,sizeof(a));
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i]=a[i]+sum[i-1];
            //cout<<sum[i]<<endl;
        }
        for(int len=2; len<=n; len++)
        {

            for(int i=1; i<=n; i++)
            {
               int j=len+i-1;
                dp[i][j]=INF;
                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
",dp[1][n]);
    }
    return 0;
}