某工程计算中要完成多个矩阵相乘（链乘）的计算任务，对矩阵相乘进行以下说明。 （1）两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。假设采用标准的矩阵相乘算法，计算，需要次乘法运算，即时间复杂度为 （2）矩阵相乘满足结合律，多个矩阵相乘时不同的计算顺序会产生不同的计算量。以矩阵，，三个矩阵相乘为例，若按计算，则需要进行次乘法运算，若按计算，则需要进行次乘法运算。 矩阵连乘问题可描述为：给定个矩阵，对较大的，可能计算的顺序数量非常庞大，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵连乘问题具有最优子结构，即若的一个最优计算顺序从第个矩阵处断开，即分为和两个子问题，则该最优解应该包含的一个最优计算顺序和的一个最优计算顺序。据此构造递归式：

其中，cost[i][j]表示的最优计算的代价。最终需要求解cost[0][n – 1]

算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算3个矩阵、4个矩阵、…、个矩阵相乘的最小计算量及最优计算顺序。下面是算法的C语言实现。 （1）主要变量说明 n：矩阵数、 seq[]：矩阵维数序列 cost[][]：二维数组，长度为，其中元素cost[i][j]表示的最优计算的计算代价 trace[][]：二维数组，长度为，其中元素trace[i][j]表示的最优计算对应的划分位置