C语言实现动态规划算法矩阵连乘的运算

下面是C语言实现动态规划算法矩阵连乘的代码：

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

void matrixChainOrder(int *p, int n, int **m, int **s) {
    int i, j, k, l, q;

    // 分配空间
    *m = (int *)malloc(sizeof(int) * n * n);
    *s = (int *)malloc(sizeof(int) * n * n);

    // 初始化m[i][i]=0，表示一个矩阵不需要进行标量乘法
    for (i = 1; i <= n; i++) {
        *((*m) + i * n + i) = 0;
    }

    // 计算m[i][j]和s[i][j]
    for (l = 2; l <= n; l++) {
        for (i = 1; i <= n - l + 1; i++) {
            j = i + l - 1;
            *((*m) + i * n + j) = INT_MAX;
            for (k = i; k < j; k++) {
                q = *((*m) + i * n + k) + *((*m) + (k + 1) * n + j) + p[i - 1] * p[k] * p[j];
                if (q < *((*m) + i * n + j)) {
                    *((*m) + i * n + j) = q;
                    *((*s) + i * n + j) = k;
                }
            }
        }
    }
}

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

int main() {
    int p[] = {30, 35, 15, 5, 10, 20, 25};  // 矩阵规模
    int n = sizeof(p) / sizeof(p[0]) - 1;  // 矩阵个数
    int *m, *s;  // 存储m[i][j]和s[i][j]

    // 计算m[i][j]和s[i][j]
    matrixChainOrder(p, n, &m, &s);

    // 输出最优括号化方案
    printf("Optimal Parenthesization: ");
    printOptimalParens(s, 1, n, n);

    // 释放空间
    free(m);
    free(s);

    return 0;
}

上述代码中，`matrixChainOrder`函数用于计算矩阵连乘问题的最优解，其中`p`是矩阵规模，`n`是矩阵个数，`m`和`s`分别存储最优解和括号位置。`printOptimalParens`函数用于输出最优的括号化方案。主函数中给出了一个示例矩阵规模以及输出最优括号化方案的示例。