DEVC++矩阵链乘法。设 A1,A2,…,An 为矩阵序列，Ai 为 Pi-1×Pi 阶矩阵，i = 1,2,…,n. 确定乘法顺序使得元素相乘的总次数最少. 输入：向量 P =<P0, P1, …, Pn> ，n个矩阵的行数、列数 实例： P = <10, 100, 5, 50> A1: 10 × 100, A2: 100 × 5, A3: 5 × 50 （可参考教材 P55-60 页）要求： （1） 写出递归公式 （2） 分析采用哪种数据结构存储中间结果 （3） 分析求解顺序 （4） 写出算法伪码 （5） 分析算法复杂度 （6） 使用熟悉的编程语言实现算法 （7） 编写测试数据，测试算法的正确性和性能

1. 递归公式：

设 Ai到Aj 的最优解为m[i][j]，则有：

m[i][j] = 0; (i = j)

m[i][j] = min{m[i][k] + m[k+1][j] + Pi-1*Pk*Pj}; (i <= k < j)

2. 中间结果存储数据结构：

采用二维数组m[i][j] 存储 Ai到Aj 的最优解。

3. 求解顺序：

从小到大枚举矩阵链长度k，然后枚举矩阵链的起点i，计算出m[i][i+k] 的值，最后得到最优解m[1][n]。

4. 算法伪码：

n = 矩阵个数
for i = 1 to n do
m[i][i] = 0
for k = 2 to n do
for i = 1 to n-k+1 do
j = i + k - 1
m[i][j] = INF
for t = i to j-1 do
q = m[i][t] + m[t+1][j] + P[i-1]*P[t]*P[j]
if q < m[i][j] then
m[i][j] = q
print(m[1][n])

5. 算法复杂度：

该算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。

6. DEVC++代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
int p[maxn], m[maxn][maxn], s[maxn][maxn];
int main()
{
    int n, i, j, k, len, q;
    cin >> n;
    for (i = 0; i <= n; i++)
        cin >> p[i];
    for (len = 2; len <= n; len++)
    {
        for (i = 1; i <= n - len + 1; i++)
        {
            j = i + len - 1;
            m[i][j] = INF;
            for (k = i; k < j; k++)
            {
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    cout << m[1][n] << endl;
    return 0;
}

7. 测试数据：

输入：4 10 100 5 50

输出：7500

输入：6 30 35 15 5 10 20 25

输出：15125

输入：3 10 100 5 50

输出：7500

输入：5 5 10 3 12 5 50 6 34 24

输出：2016