矩阵相乘的最优顺序

对于一个矩阵，进行乘法的顺序不一样，总的元素的乘法次数也不同。我们希望给出一系列矩阵之后，能找到元素乘法次数最少的计算顺序。

用动态规划来求解这个问题。

/*
 * =====================================================================================
 *
 *       Filename:  MatrixMul.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2011年12月01日 10时43分13秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  MaZheng (blog.csdn.net/mazheng1989), [e-mail]
 *        Company:  Dalian University Of Technology
 *
 * =====================================================================================
 */

#include<stdio.h>

const int n=4;
int Matrix[n][2]={20,2,2,15,15,40,40,4};
int cost[n][n];
int root[n][n];

int Proc(int i,int r,int j)
{
	return Matrix[i][0]*Matrix[r][1]*Matrix[j][1];
}
int pri(int i,int r,int j)
{
	if(i==r&&r==j)
		return -1;
	pri(i,root[i][r],r);
	pri(r+1,root[r+1][j],j);
	printf(" %d ",root[i][j]+1);

}
int main()
{
	for(int i=n-1;i>=0;i--)
	{
		for(int j=i;j<=n-1;j++)
		{
			if(j==i)
			{
				cost[i][j]=0;
				root[i][j]=i;
			      continue;
			}
			for(int r=i;r<=j-1;r++)
			{
				int temp=cost[i][r]+cost[r+1][j]+Proc(i,r,j);
				if(cost[i][j]==0)
				{
					cost[i][j]=temp;
					root[i][j]=r;
				}
				else if(cost[i][j]!=0&&cost[i][j]>=temp)
				{
					cost[i][j]=temp;
					root[i][j]=r;
				}
			}
		//	printf("%d %d %d %d \n",i+1,j+1,cost[i][j],root[i][j]+1);
		}
	}
	printf("least multiply times = %d\n",cost[0][n-1]);
	printf("compute sequece is:\n");
	pri(0,root[0][n-1],n-1);

}