矩阵连乘问题
一、问题描述
矩阵连乘算法实现；
给 定 n 个 矩 阵 ｛ A1,A2,…,An ｝ ， 其 中 Ai 与 Ai+1 是 可 乘 的 ，
i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩
阵连乘积需要的数乘次数最少。
二、问题分析
1、矩阵连乘：
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次
序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序
完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用 2 个矩
阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义
为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积 A 是完全加括号的，则
A 可 表 示 为 2 个 完 全 加 括 号 的 矩 阵 连 乘 积 B 和 C 的 乘 积 并 加 括 号 ， 即
A=(BC)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决
定着作乘积所需要的计算量。所以问题是：如何确定运算顺序，可以使计算量
达到最小化。但穷举法不是一个有效的算法，所以用动态规划法解矩阵连乘积
的最优计算次序问题。如下：1、分析最优解结构 2、建立递归关系 3、计算最
优质 4、构造最优解
三、算法流程（图）
