【实验目的】
应用动态规划算法思想求解矩阵连乘的顺序问题。
【实验性质】
验证性实验。
【实验要求】
应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义：
0 （ i=j ）
m[i][j]=
min{m[i][k]＋ m[k+1][j]+ni-1nknj （ i<j）
要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。
【实验内容】
对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2，… ，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di (1≤i≤n)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成测试。
【算法思想及处理过程】
第一行引入了iostream和climits两个库，分别用于输入输出和定义整数类型的最大最小值。
使用了命名空间std，避免了每个标准库函数都加上std::的麻烦。
定义了一个MatrixChain类，包含了私有成员变量p, m, s和n，以及公有的构造函数和成员函数。
构造函数MatrixChain接受两个参数，一个是矩阵个数mSize，另一个是一个整型数组q，用于存储矩阵的行列式值。在构造函数中，首先将参数mSize赋值给私有成员变量n，然后动态分配一个大小为n+1的整型数组p，并将参数q的值赋给p。接下来，分别动态分配大小为n的二维整型数组m和s。
成员函数MChain用于使用一般动态规划法求解最优解值。首先对m的主对角线上的元素进行初始化为0。然后使用两个嵌套循环，从矩阵个数为2开始，依次求解m[i][j]和s[i][j]，其中m[i][j]表示从第i个矩阵到第j个矩阵链的最小乘法次数，s[i][j]表示从第i个矩阵到第j个矩阵链的最优划分位置。在内层循环中，还有一个嵌套循环，用于遍历所有可能的划分位置，更新最小乘法次数和最优划分位置。
成员函数Traceback用于构造最优解的公有函数。它调用私有递归函数Traceback(int i, int j)来构造最优解。如果i等于j，则说明只有一个矩阵，直接输出"A"，否则，递归调用Traceback函数，同时在合适的位置输出"("和")"符号。
成员函数Traceback(int i, int j)是私有递归函数，用于构造最优解。递归终止条件是i等于j，输出"A"。否则，如果i小于s[i][j]，输出"("，然后递归调用Traceback函数，再输出")"。然后判断s[i][j]+1是否小于j，如果是，输出"("，再递归调用Traceback函数，最后输出")"。
主函数main首先输入矩阵个数n，并提示输入行列式值。然后动态分配大小为n+1的整型数组q，用于存储行列式值。接下来使用循环将输入的值赋给数组q。然后创建一个MatrixChain对象mc，传入n和q作为参数。调用mc的成员函数MChain求解最优乘法次数，并将结果赋给变量minMult。然后输出最少乘法次数和最优连乘积次序，最后释放数组q的内存。
主函数结束，返回0。
【程序代码】
#include <iostream>
#include <climits>
using namespace std;
class MatrixChain {
public:
MatrixChain(int mSize, int* q); //创建二维数组m和s，一维数组p，并初始化
int MChain(); //一般动态规划法求最优解值
int LookupChain(); //备忘录方法求最优解值（程序7-4）
void Traceback(); //构造最优解的公有函数
private:
void Traceback(int i, int j); //构造最优解的私有递归函数
int LookupChain(int i, int j); //备忘录方法私有递归（程序7-4）
int* p, ** m, ** s, n;
};
MatrixChain::MatrixChain(int mSize, int* q) {
n = mSize;
p = new int[n + 1];
for (int i = 0; i <= n; i++) {
p[i] = q[i];
}
m = new int* [n];
for (int i = 0; i < n; i++) {
m[i] = new int[n];
}
s = new int* [n];
for (int i = 0; i < n; i++) {
s[i] = new int[n];
}
}
int MatrixChain::MChain() {
for (int i = 0; i < n; i++) {
m[i][i] = 0;
}
for (int r = 2; r <= n; r++) {
for (int i = 0; i <= n - r; i++) {
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i] * p[i + 1] * p[j + 1];
s[i][j] = i;
for (int k = i + 1; k < j; k++) {
int t = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
return m[0][n - 1];
}
void MatrixChain::Traceback(int i, int j)
{
if (i == j) { cout << 'A' << i+1; return; }
if (i < s[i][j]) cout << '('; Traceback(i, s[i][j]); if (i < s[i][j])cout << ')';
if (s[i][j] + 1 < j)cout << '('; Traceback(s[i][j] + 1, j); if (s[i][j] + 1 < j) cout << ')';
}
void MatrixChain::Traceback()
{
cout << '('; Traceback(0, n-1 ); cout << ')';
cout << endl;
}
int main() {
int n;
cout << "请输入矩阵个数：";
cin >> n;
cout << "输入行列式值：" << endl;
int* q = new int[n + 1];
for (int i = 0; i <= n; i++)
{
cin >> q[i];
}
MatrixChain mc(n, q);
int minMult = mc.MChain();
cout << "最少乘法次数: " << minMult << endl;
cout << "最优连乘积次序: ";
mc.Traceback();
delete[] q;
return 0;
}
【运行结果】
【算法分析】
一般动态规划法求最优解值的MChain函数的时间复杂度为O(n^3)，空间复杂度为O(n^2)。
备忘录方法求最优解值的LookupChain函数的时间复杂度为O(n^3)，空间复杂度为O(n^2)。
构造最优解的Traceback函数的时间复杂度为O(n)，空间复杂度为O(1)。
