问题：

给定n个矩阵{A1,A2,A3,……,An}，其中 Ai 与 Ai+1 是可乘的。由于矩阵乘法满足结合律，故计算矩阵的连乘可以有许多种不同的顺序。如何确定矩阵连乘积的计算次序，使得依次序计算矩阵连乘积需要的数次数最少。

分析：

　　为了方便起见，将矩阵连成积 Ai·Ai+1·……·Aj 简记作 A[i:j]。

　　则原问题就是计算 A[1:n] 的最计算次数。

　对于矩阵 A[i:j] ，设所需的最少数乘次数为 m[i][j]。

　　则原问题的最优值就是 m[1][n]。

　　若最优解是在矩阵 Ak 和 Ak+1 中间断开，则 A[1:n] 的计算量= A[1:k] 的计算量 + A[k+1:n] 的计算量 + 矩阵 A[1:k] 和 A[k+1:n] 相乘的计算量。

　　则（k 为使得 m[i][j] 最小的值）：

算法思路：

　　我们先计算 m[i][i+1] 的值（即长度为 2 的），那接下来计算 m[i][i+2] 的值（长度为3的）就可以利用前面m[i][i+1] 的值了。

　　比如我们先计算 m[1][2] 、m[2][3] 、m[3][4]…… 然后计算 m[1][3] 、 m[2][4]……

　　然后接着计算长度更长的，不断搞，直到计算到 m[1][n]，就是我们所要的值。

　　动态规划就是从最小的子问题出发，一直算到最顶层的父问题。

代码：

void MatrixChain(int *p, int n, int **m, int **s)//矩阵 Ai 的维数为 pi-1 * pi
{
    for (int i = 1; i <= n; i++) m[i][i] = 0;//初始化，A[i:i] 就是单一的一个矩阵，没有计算次数
    for (int r = 2; r <= n; r++)
    {//r代表 计算长度，先从长度为2的开始算
        for (int i = 1; i <= n; i++)
        {
            int j = r + i - 1;
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];//先给m[i][j]赋个初值
            s[i][j] = i;
            for (int k = i + !; k < j; k++)
            {//从 i 到 k 中寻找使得 m[i][j] 最小的值，替换原来的m[i][j]
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}