南邮动态规划法：矩阵连乘备忘录与代码详解

这段代码是关于南邮大学动态规划法实验的一个矩阵连乘问题的实现，主要涉及到矩阵链乘（Matrix Chain Multiplication）的优化算法。矩阵链乘是一个经典的计算问题，它要求找到最优的顺序来连接一系列矩阵，以便在最小化总乘法次数的同时进行计算。这个问题通常通过动态规划方法解决，其中备忘录法（Memoization）被用来避免重复计算。 代码定义了一个名为`MatrixChain`的类，用于表示矩阵链及其操作。该类有以下几个关键成员函数： 1. `MatrixChain(int mSize, int*q)`: 构造函数，接收矩阵的数量（mSize）和对应矩阵大小数组（q）。在这个函数中，初始化了长度为n+1的整型数组p来存储中间结果，以及两个二维数组m和s，分别用于存储矩阵乘法的最小代价和上一状态的索引。 2. `MChain()`: 主函数，实现了动态规划的核心算法。它首先初始化m和s数组为0，然后通过两层循环计算矩阵链的最小乘法代价。外层循环控制链的长度，内层循环则遍历所有可能的起始和结束节点。在每次迭代中，它会更新最小代价（m[i][j]）和相应的状态索引（s[i][j]）。 3. `LookupChain()`: 动态查找函数，用于获取已计算过的最小代价，如果未计算则调用`MChain()`进行计算。 4. `Traceback()`: 回溯函数，当计算出最小代价后，使用状态索引来确定最优的矩阵连接顺序。 5. `Initialise()`: 初始化函数，设置所有矩阵间的初始代价和状态为0。 6. `Output()`: 可能的输出函数，用于打印最终的结果或执行其他与输出相关的操作。 代码的关键在于`MChain()`函数中的计算逻辑，通过比较不同路径的成本，逐步构建出全局最优解。这种方法有效地减少了重复计算，提高了效率。整个过程展示了如何将一个复杂的计算问题分解为更小的部分，并通过动态规划策略找出最佳解决方案。 总结来说，这段代码是南邮大学算法实验中矩阵连乘问题的备忘录动态规划实现，旨在教学学生如何运用算法技巧来优化矩阵运算，并且提供了一种可扩展的框架，适用于处理更大的矩阵链问题。