//計算最優值
#include<iostream>
using namespace std;
void MatrixChain(int *p,int n,int  (*m)[7],int (*s)[7]);
void main()
{
	cout<<"\t\t\t*****************************"<<endl;
	cout<<"\t\t\t     動態規劃--計算最優值"<<endl;
	cout<<"\t\t\t          2007.04.15"<<endl;
	cout<<"\t\t\t*****************************"<<endl;
	int SourceDataArray[7][7];
	int ObjectDataArray[7][7];
	int DataArray[7]={30,35,15,5,10,20,25};
	//for(unsigned short int displacement=;displacement<)
	
	for(unsigned short int horizonal=1;horizonal<7;horizonal++)
	{
		for(unsigned short int vertical=1;vertical<7;vertical++)
		{
			SourceDataArray[horizonal][vertical]=ObjectDataArray[horizonal][vertical]=-1;
		}
	
	}
	
	MatrixChain(DataArray,6,ObjectDataArray,SourceDataArray);
	
	for(horizonal=1;horizonal<7;horizonal++)
	{
		for(unsigned short int vertical=1;vertical<7;vertical++)
		{
			if(ObjectDataArray[horizonal][vertical]==-1)
			{
				cout<<' '<<'\t';
			}
			else
			{	
				cout<<ObjectDataArray[horizonal][vertical]<<'\t';
			}
		}
		cout<<endl;
	}
	cout<<endl<<endl;
	for(horizonal=1;horizonal<7;horizonal++)
	{
		for(unsigned short int vertical=1;vertical<7;vertical++)
		{
			if(SourceDataArray[horizonal][vertical]==-1)
			{
				cout<<' '<<'\t';
			}
			else
			{	
				cout<<SourceDataArray[horizonal][vertical]<<'\t';
			}
		}
		cout<<endl;
	}
}
void MatrixChain(int *p,int n,int (*m)[7],int (*s)[7])
{
	
	for(int i=1;i<=n;i++)
	{
		s[i][i]=m[i][i]=0;
	}
	for(int r=2;r<=n;r++)//作8次循環
	{
		
		for(int i=1;i<=n-r+1;i++)//r=2,n=7,作6次循環
		{
			
			int j=i+r-1;//j=1+2-1=2
		
		m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
		s[i][j]=i;
		for(int k=i+1;k<j;k++)
		{
			int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[i];
			
			if(t<m[i][j])
			{
				m[i][j]=t;
				s[i][j]=k;
			
			}
		
		
		}
	
		}
	}




}