用c++写一个矩阵链乘法

以下是用 C 语言实现矩阵链乘法的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

void matrixChainOrder(int p[], int n, int m[][MAX_SIZE], int s[][MAX_SIZE]) {
int i, j, k, l, q;
for (i = 1; i <= n; i++) {
m[i][i] = 0;
}
for (l = 2; l <= n; l++) {
for (i = 1; i <= n - l + 1; i++) {
j = i + l - 1;
m[i][j] = 2147483647;
for (k = i; k <= j - 1; 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;
}
}
}
}
}

void printOptimalParens(int s[][MAX_SIZE], int i, int j) {
if (i == j) {
printf("A%d", i);
} else {
printf("(");
printOptimalParens(s, i, s[i][j]);
printOptimalParens(s, s[i][j] + 1, j);
printf(")");
}
}

int main() {
int p[] = {30, 35, 15, 5, 10, 20, 25};
int n = sizeof(p) / sizeof(p[0]) - 1;
int m[MAX_SIZE][MAX_SIZE], s[MAX_SIZE][MAX_SIZE];
matrixChainOrder(p, n, m, s);
printf("Optimal Parenthesization: ");
printOptimalParens(s, 1, n);
printf("\nMinimum Number of Multiplications: %d\n", m[1][n]);
return 0;
}

这个程序可以计算矩阵链乘法的最小代价，并输出最优的括号化方案。