矩阵乘法代码

void MatrixChain(int p[], int n, int **m, int **s) {
    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][i] + m[i+1][j] + p[i-1]*p[i]*p[j]; // 本轮循环中的初始化
            s[i][j] = i; // 初始化最优划分位置

            for (int k = i + 1; k < j; k++) { // 寻找最优分割位置进行测试
                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;
                }
            }
        }
    }
}

n-r+1是我们可以构造的子链的长度