1.矩阵连乘问题的定义
1.1 给定 n 个矩阵的连乘积 A1A2...An，因为矩阵乘法满足结合律，所以计算矩阵的连乘积可以有不同的计算次序（这个次序的组合数满足卡特兰数），采用不同的计算次序计算的数乘次数也不相同。例如，A1A2A3，这三个矩阵的维数分别是10*100,100*5，和5*50，若先计算A1A2，总的计算次数为10*100*5+10*5*50 = 7500，然而先计算A2A3，总的计算次数为 100*5*50 + 10*100*50 = 75000，可见计算数乘次数相差10倍。这里我们用加括号的方式来表示矩阵的计算次序。每一种完全加括号方式对应一种矩阵的计算次序；
1.2 什么是完全加括号的矩阵连乘积？完全加括号的矩阵连乘积可以递归的定义为(见《计算机算法分析与设计》)：
a）单个矩阵是完全加括号的；
b）矩阵连乘积 A 是完全加括号的，则 A 可以表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A =(BC)。
2.矩阵连乘问题的求解
2.1 设矩阵连乘积A1A2...An，Ai的维数分别为 p[i-1]*p[i]，m[i][j]为AiAi+1...Aj的最少数乘次数，它满足下述递归关系:
a)m[i][j] = 0 , i == j;
b)m[i][j] = min{m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]}, i<= k < j;
2.2 根据上述递归式可以写出本问题的递归方法，这里为了求出最终的计算次序，需要用一个二维数组 s 保存每次断开的位置。
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#define MAX 100
using namespace std;
int MatrixChain(int i, int j, int *p, int (*m)[MAX], int (*s)[MAX]);
void TraceBack(int i, int j, int (*s)[MAX]);
int main(int argc, const char *argv[])
{
int p[MAX], m[MAX][MAX], s[MAX][MAX];
int n;
cin >> n; //矩阵的个数
int i ;
for(i = 0; i <= n; i++){ //相乘矩阵链的行列数
cin >> p[i];
}
memset(m, -1, sizeof m);
MatrixChain(1, n, p, m, s);
TraceBack(1, n, s);
cout << endl;
return 0;
}
int MatrixChain(int i, int j, int *p, int (*m)[MAX], int (*s)[MAX]){
if(m[i][j] != -1)
return m[i][j];
if(i == j)
return 0;
else{
int k, min = 1000000;
for(k = i; k < j; k++){
m[i][k] = MatrixChain(i, k, p, m, s);
m[k+1][j] = MatrixChain(k+1, j, p, m, s);
int tmp = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
if(tmp < min){
min = tmp;
s[i][j] = k;
}
}
return min;
}
}
void TraceBack(int i, int j, int (*s)[MAX]){
if(i == j){
cout << "A" << i;
return;
}
cout << "(";
TraceBack(i, s[i][j], s);
cout << "*";
TraceBack(s[i][j] + 1, j, s);
cout << ")";
}
2.3 矩阵连乘的非递归方法其实就是一个填充表格的过程，以6个矩阵的乘积为例，矩阵的维度分别为p[] = {30, 35, 15, 5, 10, 20, 25},如下图所示，这里先将 m[i][i] 设置为 0， 之后再以正对角线方向根据上述递归式计算m[1][2],m[2][3]...m[5][6]等等，例如m[2][3] = m[2][2] + m[3][3] + p[1] * p[2] *p[3] = 0 + 0 + 30 * 35 * 15 = 15750,这里只能以2分割, 再例如计算 m[2][5] ，此时要分别计算出 m[2][2] + m[3][5] + p[1] * p[2] * p[5], m[2][3] + m[4][5] + p[1] * p[3] * p[5], 以及 m[2][4] + m[5][5] + p[1] * p[4] * p[5]，然后求其最小值即为 m[2][5]。填充后的表格和源程序如下：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 15750 | 7875 | 9375 | 11875 | 15125 |
| 2 | 0 | 2625 | 4375 | 7125 | 10500 | |
| 3 | 0 | 750 | 2500 | 5375 | ||
| 4 | 0 | 1000 | 3500 | |||
| 5 | 0 | 5000 | ||||
| 6 | 0 |
#include <iostream>
#include <string>
#include <vector>
#define MAX 100
using namespace std;
void MatrixChain(int *p, int n, int (*m)[MAX], int (*s)[MAX]);
void TraceBack(int i, int j, int (*s)[MAX]);
int main(int argc, const char *argv[])
{
int p[MAX], m[MAX][MAX], s[MAX][MAX];
int n;
cin >> n; //矩阵的个数
int i ;
for(i = 0; i <= n; i++){ //相乘矩阵链的行列数
cin >> p[i];
}
MatrixChain(p, n, m, s);
TraceBack(1, n, s);
cout << endl;
return 0;
}
void MatrixChain(int *p, int n, int (*m)[MAX], int (*s)[MAX]){
int i;
for(i = 1; i <= n; i++)
m[i][i] = 0;
int r; //外层循环的次数
for(r = 2; r <= n; r++){
for(i = 1; i<= n - r + 1; i++){ //求解m[i][j]
int j = i + r -1;
int min = m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j];
s[i][j] = i;
int k;
for(k = i + 1; k < j; k++){
int tmp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(tmp < min){
min = tmp;
s[i][j] = k;
}
}
m[i][j] = min;
}
}
}
void TraceBack(int i, int j, int (*s)[MAX]){
if(i == j){
cout << "A" << i;
return;
}
cout << "(";
TraceBack(i, s[i][j], s);
cout << "*";
TraceBack(s[i][j] + 1, j, s);
cout << ")";
}
3.小结
3.1 和最长公共子序列问题相同，当我们使用动态规划来求解某一个问题时，这个问题一般都具有两个明显特征，一是最优子结构性质，即问题的最优解包含了子问题的最优解，二是子问题重叠，即在递归求解时，有些子问题被重复计算。
3.2 针对上述子问题重叠的性质，我们使用了备忘录方法，即在递归的过程中将每个子问题的结果保存在数组中，如果下次需要直接从数组中取出，从而避免了重复计算。