C语言实现矩阵连乘最优加括号方式的求解

矩阵连乘问题是一个经典的动态规划问题，它的目标是找到一种最优的加括号方案，使得矩阵乘法的计算量最小。其状态转移方程为：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] }

其中，`dp[i][j]` 表示从第 `i` 个矩阵乘到第 `j` 个矩阵的最小代价，`p[i]` 表示第 `i` 个矩阵的行数，以及第 `i+1` 个矩阵的列数。

下面是 C 语言实现矩阵连乘最优加括号方案的代码：

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

#define N 10

int dp[N][N];   // 存储最小代价
int s[N][N];    // 存储最优解

void matrix_chain_order(int p[], int n) {
    int i, j, k, l;
    for (i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    for (l = 2; l <= n; l++) {
        for (i = 1; i <= n-l+1; i++) {
            j = i + l - 1;
            dp[i][j] = INT_MAX;
            for (k = i; k <= j-1; k++) {
                int q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < dp[i][j]) {
                    dp[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 p[] = {30, 35, 15, 5, 10, 20, 25};
    int n = sizeof(p) / sizeof(int) - 1;   // 矩阵个数
    matrix_chain_order(p, n);
    printf("最小代价：%d\n", dp[1][n]);
    printf("最优加括号方案：");
    print_optimal_parens(1, n);
    printf("\n");
    return 0;
}

上述代码实现了矩阵连乘最优加括号方案的求解，并输出了最小代价以及最优加括号方案。其中，`p[]` 数组表示矩阵的行列数，`n` 表示矩阵的个数。`matrix_chain_order()` 函数实现了动态规划的过程，`print_optimal_parens()` 函数实现了输出最优加括号方案的过程。