矩阵链乘积动态规划求解及其优化实现（C语言版本）

题目： 确定n个矩阵连乘积 A1A2A3…An 的计算次序 ，使得按照这一次序计算矩阵连乘积，需要的"数乘"次数最小。

• 此问题具备动态规划的适用条件
• 矩阵乘法符合结合律
• 当两个矩阵相乘时，必须满足前一个矩阵的列数等于后一个矩阵的行数
• 当两个矩阵相乘时，所需的运算量为：前一个矩阵的行数 乘以 前一个矩阵的列数（即：后一个矩阵的行数）乘以 后一个矩阵的列数
• 实际上该问题并非执行具体的乘法操作，而是确定相关矩阵相乘时的操作顺序

思路：
将连续相乘的一组矩阵表示为 { P(i-1), Pi, P(i+1), … , Pk, … , Pj } ：

• P(i-1) 表示的是第i个矩阵Ai的行数
• Pi 表示的是第i个矩阵Ai的列数 ，同时也是第i+1个矩阵A(i+1)的行数
• P(i+1) 表示的是第i+1个矩阵A(i+1)的列数
• 即：{P(i-1), Pi, P(i+1)} 所描述的是两个相邻矩阵Ai与A(i+1)之间的相乘关系

假定在连续相乘的一组表达式 A[i:j] 中，最优计算方式最后一次合并发生在Ak与A(k+1)之间，
k的位置共有j-1种可能情况
所需计算总量为：A[i:k] 的最优计算总量加上 A[k+1:j] 的