矩阵连乘问题(备忘录法).cpp

动态规划解一系列经典问题

//矩阵连乘问题(备忘录法)

#include <iostream.h>
#include <iomanip.h>
#define N 6
int p[N+1]={30,35,15,5,10,20,25},m[N][N]={0}, s[N][N]={0};

void Output(int n, int a[N][N])
{
	for(int i=1; i<=n-1; i++)
	{
		cout<<endl<<setw(8*i-7)<<0;
		for(int j=i+1; j<=n; j++)
			cout<<'\t'<<a[i][j];
	}
	cout<<endl<<setw(8*i-7)<<0<<endl;
}

int LookupChain(int i, int j)
{
	if (m[i][j]>0) return m[i][j];
	if (i==j) return 0;
	int u=LookupChain(i+1, j)+p[i-1]*p[i]*p[j];
	s[i][j]=i;
	for (int k=i+1; k<j; k++)
	{
		int t=LookupChain(i, k)+LookupChain(k+1, j)+p[i-1]*p[k]*p[j];
		if (t<u)
		{
			u=t;
			s[i][j]=k;
		}
	}
	m[i][j]=u;
	return u;
}

void Traceback(int i, int j)
{
	if (i==j) return;
	Traceback(i, s[i][j]);
	Traceback(s[i][j]+1, j);
	cout<<"A("<<i<<","<<s[i][j]<<") & A("<<s[i][j]+1<<","<<j<<")"<<endl;
}

void main()
{
	LookupChain(1, N);
	Output(N, m);
	Output(N, s);
	cout<<"Multiplay Order:"<<endl;
	Traceback(1, N);
}