#include"iostream.h"

void matrixChain(int p[], int m[],int s[],int n){
	//n個矩陣相乘A0*A1*A2*...*An-1
	//A0的大小為p[0]*p[1],A1的大小為p[1]*p[2]
	//m大小為n*n, m[i*n+j]存儲的是Ai*...*Aj的最小數乘次數
	//s大小為n*n, s[i*n+j]存儲矩陣鏈Ai*...*Aj斷開的最佳方式
	//先計算m[i][i]=0,i=0,1,...,n-1,然后，根據遞歸式，按矩陣鏈遞增的方式依次計算m[i][i+1],i=0,1,...,n-2,(矩陣鏈長度為2)；
	//m[i][i+2],i=0,1,...,n-3,(矩陣鏈長度為3)；
	int i,j,r,k,t;
	for(i=0;i<n;i++) m[i*n+i]=0;
	for(r=2;r<=n;r++){
		for(i=0;i<n-r+1;i++){
			j=i+r-1;
			m[i*n+j]=m[(i+1)*n+j]+p[i]*p[i+1]*p[j+1];
			s[i*n+j]=i;
			for(k=i+1;k<j;k++){
				t=m[i*n+k]+m[(k+1)*n+j]+p[i]*p[k+1]*p[j+1];
					if(t<m[i*n+j]){
						m[i*n+j]=t;
						s[i*n+j]=k;
					}
			}
		}
	}
}

void traceback(int s[], int i, int j, int n){
	if(i==j) return;
	traceback(s, i, s[i*n+j], n);
	traceback(s, s[i*n+j]+1, j, n);
	cout<<"Multiply A"<<i<<","<<s[i*n+j]<<"and A"<<s[i*n+j]+1<<","<<j<<endl;
}

void main()
{
	int n=6;
	int p[7]={30,35,15,5,10,20,25};
	int m[36]={0};
	int s[36]={0};
	matrixChain(p,m,s,n);
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++)
			cout<<m[i*n+j]<<"  ";
		cout<<endl;
	}
	traceback(s,0,n-1,n);
}