[ 算法 ] 矩阵连乘

问题

矩阵是按行和列排列的数字集合。矩阵A（r行s列）和矩阵B（p行q列）能够相乘的条件为s=p，即前一个矩阵的列数要等于后一个矩阵的行数。完成乘法AB共需要rsq次乘法。举证乘法满足结合律，但不满足交换律，即一般情况下AB和BA并不相等，但(AB)C和A(BC)的结果是一样的。现有n个矩阵连乘，记为A_1A_2...A_n_A_1_A_2..._An_，A_1_A_1的行列分别为p_0_p_0和p_1_p_1，A_2_A_2的行列为p_1_p_1和p_2_p_2，以此类推。请设计算法，给出矩阵连乘的顺序，使总计算量最小。总计算量为每次矩阵相乘的乘法次数之和。

代码

#include <stdio.h>
long long int m[1500][1500], s[1500][1500];
void matrixchain(long long int* p, int n)
{
    long long int t;
    for (int i = 1; i <= n; i++)m[i][i] = 0;
    for (int r = 2; r <= n; r++) {
        for (int i = 1; i <= n - r + 1; i++) {
            int j = i + r - 1;
            m[i][j] = m[i][j] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
            s[i][j] = i;
            for (int k = i + 1; k < j; k++) {
                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;
                }
            }
        }
    }
}

int main() {
    int n;
    long long int p[1500];
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
        scanf("%d", &p[i]);
    matrixchain(p, n);
    printf("%lld", m[1][n]);
    return 0;
}