【算法设计与分析】 矩阵连乘（动态规划）

【算法设计与分析】 矩阵连乘（动态规划）

【问题描述】
使用动态规划算法解矩阵连乘问题，具体来说就是，依据其递归式自底向上的方式进行计算，在计算过程中，保存已子问题答案，每个子问题只解决一次，在后面计算需要时只要简单查一下得到其结果，从而避免大量的重复计算，最终得到多项式时间的算法。

【输入形式】
在屏幕上输入第1个矩阵的行数和第1个矩阵到第n个矩阵的列数，各数间都以一个空格分隔。

【输出形式】
矩阵连乘A1…An的最少数乘次数和最优计算次序。

【样例输入】

30 35 15 5 10 20 25

【样例输出】

15125
((A1(A2A3))((A4A5)A6))

【样例说明】
输入：第1个矩阵的行数和第1个矩阵到第6个矩阵的列数，以空格分隔。
输出：矩阵连乘A1…An的最少数乘次数为15125，最优计算次序为((A1(A2A3))((A4A5)A6))。

【题解代码】

Python代码：

def MatrixChain(p,n,m,s):
    for i in range(1,n+1):
        m[i][i]=0
    for r in range(2,n+1):
        for i in range(1,n-r+2):
            j=i+r-1
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]
            s[i][j]=i
            for k in range(i+1,j):
                t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
                if t<m[i][j]:
                    m[i][j]=t
                    s[i][j]=k

def Traceback(i,j,s):
    if i==j:
        print("A",i,sep="",end="")
        return
    print("(",end="")
    Traceback(i,s[i][j],s)
    Traceback(s[i][j]+1,j,s)
    print(")",end="")

p=[int(i) for i in input().split(" ")]
n=len(p)-1
m=[[0 for i in range(n+1)] for j in range(n+1)]
s=[[0 for i in range(n+1)] for j in range(n+1)]
MatrixChain(p,n,m,s)
print(m[1][n])
Traceback(1,n,s)

C++代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
using namespace std;
int p[100],m[100][100],s[100][100];
int Left[100],Right[100];//记录答案中输出的左右括号数 

/*
int pow(int x,int n)//快速幂 
{
	int base=x,res=1;
	while(n>0)
	{
		if(n&1)
			res*=base;
		n>>=1;
		base*=base;
	}
	return res;
}

string int_to_string(int a)//将整数转换为字符串 
{
	if(a==0) return "0";
	string b;
	int pos=0;
	while(pow(10,pos)<a)
		pos++;
	while(--pos>=0)
	{
		b+=a/pow(10,pos)+'0';
		a%=pow(10,pos);
	}
	return b;
}
*/

void MatrixChain(int p[],int n,int m[][100],int s[][100])
{
	for(int i=1;i<=n;i++)
		m[i][i]=0;
	for(int r=2;r<=n;r++)
	{
		for(int i=1;i<=n-r+1;i++)
		{
			int j=i+r-1;
			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[j];
				if(t<m[i][j])
				{
					m[i][j]=t;
					s[i][j]=k;
				}
			}//找到最优断开位置 
		}
	}
}

void Traceback(int i,int j,int s[][100])
{
	//if(i==j) return;
	if(i==j)
	{
		cout<<"A"<<i;
		return;
	}
	cout<<"(";
	Traceback(i,s[i][j],s);
	Traceback(s[i][j]+1,j,s);
	cout<<")";
	//cout<<"Multiply A"<<i<<", "<<s[i][j]<<" and A"<<s[i][j]+1<<", "<<j<<endl;
	/*
	if(i<s[i][j])
	{
		Left[i]++;
		Right[s[i][j]]++;
	} 
	if(s[i][j]+1<j)
	{
		Left[s[i][j]+1]++;
		Right[j]++;
	}//加上计算当中的括号 
	*/
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string str;
	stringstream scin;
	getline(cin,str);
	scin<<str;
	int t,num=-1;
	while(scin>>t)
		p[++num]=t;
	MatrixChain(p,num,m,s);
	cout<<m[1][num]<<endl;//输出最优值答案 
	Traceback(1,num,s);
	/*
	cout<<"(";
	for(int i=1;i<=num;i++)
	{
		for(int j=0;j<Left[i];j++)
			cout<<"(";
		cout<<"A"<<i;
		for(int j=0;j<Right[i];j++)
			cout<<")";
	}
	cout<<")"<<endl;//输出最优计算次序 
	*/
	return 0;
}