nyist 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;
}