nyist 737 인접 돌 합병 문제

http://acm.nyist.net/JudgeOnline/problem.php?pid=737
동적 계획 상태 방정식:
dp[i][j]=d[i][k]+dp[k+1][j]+(sum[k]-sum[i-1])+(sum[j]-sum[k])
경계: 0 < = i, j < = n, i < = k < j
           if(i==j)    dp[i][j]=0;
   sum [i] = 앞 i 개수 의 합.
 

#include <iostream>

#include <cstring>

using namespace std;

int dp[205][205],a[205],sum[205];

int f(int i,int j)

{

	int k,ans;

	if(dp[i][j]>=0) return dp[i][j];

	if(i==j) return dp[i][j]=0;

	for(k=i;k<j;k++)

	{

		if(dp[i][j]<0) dp[i][j]=1000000005;

		ans=f(i,k)+f(k+1,j)+(sum[k]-sum[i-1])+(sum[j]-sum[k]);

		if(ans<dp[i][j]) dp[i][j]=ans;	

	}

	return dp[i][j];

}

int main(int argc, char *argv[])

{

	int n,i,j,k;

	while(cin>>n)

	{

		for(i=1;i<=n;i++) {cin>>a[i];sum[i]=a[i]+sum[i-1];}

		memset(dp,-1,sizeof(dp));	

		cout<<f(1,n)<<endl;

	}

	return 0;

}