动态规划矩阵连乘C++代码

#include <stdio.h>
#include <limits.h>

#define MAX_N 100

int n;
int p[MAX_N + 1];
int m[MAX_N + 1][MAX_N + 1], s[MAX_N + 1][MAX_N + 1];

void matrix_chain_order() {
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] = INT_MAX;
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;
}
}
}
}
}

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

int main() {
int i;
scanf("%d", &n);
for (i = 0; i <= n; ++i)
scanf("%d", &p[i]);
matrix_chain_order();
printf("%d\n", m[1][n]);
print_optimal_parens(1, n);
printf("\n");
return 0;
}