矩阵连乘问题动态规划算法

内容： n个矩阵连乘，不满足交换律，但是满足结合律，通过不同的加括号方式，会使得需要的乘法次数不同。用动态规划方法计算，找出最优加括号方式，使总的乘法次数最少。

下面我们考虑用动态规划求解。
预处理：
将矩阵连乘积AiAi+1…Aj简记为A[i:j]，这里i≤j。
考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为（AiAi+1… Ak）（Ak+1 Ak+2… Aj ）。
计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。
分析最优解的结构
特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。
当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n。
当i<j时，m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj，这里Ai的维数为pi-1×pi。
可以递归地定义m[i,j]为：

C++代码的实现如下：

#include<iostream>
#include<iomanip>
using namespace std;
const int sz= 20;
void MatrixChain(int *p, int m[sz][sz], int s[sz][sz], int length) {
	//m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0;
	for (int i = 1;i<= length; i++) {
		 m[i][i] = 0;    //把矩阵得对角线上得元素都赋值为0
	   }
	//r=2为对角线紧邻的右上位置，随着r的增大，即沿着右上角的方向递增，扩大链的长度
	for (int r = 2; r <= length; r++) {
		for (int i = 1; i <= length;i++) {
			 int j = i + r - 1;//以i为起始位置，j为长度为r的链的末位，
			m[i][j] = m[i + 1][j]+ p[i - 1] * p[i] * p[j];//将k=i的位置的大小
			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 printMatrix(int m[sz][sz] ,int length) {
	for (int i = 1; i <= length; i++) {
		for (int j = 1; j <= length; j++) {
		cout << setw(6) << setfill(' ') << m[i][j] << "   ";
		}
		cout << endl;
	}
}
//通过递归输出最优的划分
void printresult(int s[sz][sz], int i, int j) {
	if (i == j)//只有一个矩阵，直接输出
	{
		cout << "A" << i;
	}
	else//是否需要再添加一种情况：两个矩阵，加括号输出？？
	{
		cout << "(";
		printresult(s, i, s[i][j]);//递归，从得到最优解的地方开始s[i][j]处断开
		printresult(s, s[i][j] + 1, j);
		cout << ")";
	}
}
int main() {
	int n;
	int p[sz], m[sz][sz], s[sz][sz];
	//将数组赋初始值为0
	memset(p, 0, sizeof(p));
	memset(m, 0, sizeof(m));
	memset(s, 0, sizeof(s));
	cout << "请输入矩阵的个数:" ;
	cin >> n;
	for (int i = 0; i <= n; i++) {
		cout << "请输入"<<(i+1)<<"的下标：";
		cin >> p[i];
	}	
	cout << "你输入的矩阵为：" << endl;
	for (int i = 0; i <n; i++) {
		cout << "A" << (i + 1) << "[" << p[i] << "]"
			<< "[" << p[i + 1] << "]  ";
	}
	cout << endl;
	cout << "m矩阵为：" << endl;
	MatrixChain(p, m, s, n);
	printMatrix(m, n);
	cout << "s矩阵为：" << endl;
	printMatrix(s, n);
	printresult(s, 1, n);
	system("pause");
	return  0;
}

运行结果为：