计算矩阵连乘积的备忘录算法c++代码

以下是计算矩阵连乘积的备忘录算法的C代码：

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

#define MAX_SIZE 100

int matrix[MAX_SIZE][MAX_SIZE]; // 存储矩阵的维数
int memo[MAX_SIZE][MAX_SIZE]; // 存储已计算过的中间结果

int matrixChainOrder(int p[], int i, int j) {
    if (i == j) {
        return 0; // 矩阵本身不需要乘
    }
    if (memo[i][j] != -1) {
        return memo[i][j]; // 如果已经计算过，则直接返回中间结果
    }
    int minCost = INT_MAX;
    for (int k = i; k < j; k++) {
        int cost = matrixChainOrder(p, i, k) + matrixChainOrder(p, k+1, j) + p[i-1]*p[k]*p[j];
        if (cost < minCost) {
            minCost = cost;
        }
    }
    memo[i][j] = minCost; // 记录中间结果
    return minCost;
}

int main() {
    int n; // 矩阵的个数
    printf("请输入矩阵的个数：");
    scanf("%d", &n);
    printf("请依次输入每个矩阵的维数：\n");
    for (int i = 0; i <= n; i++) {
        scanf("%d", &matrix[i][i]);
    }

    // 初始化备忘录
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            memo[i][j] = -1;
        }
    }

    printf("矩阵连乘积的最小代价为：%d\n", matrixChainOrder(matrix, 1, n));
    return 0;
}

在这个代码中，我们首先定义了两个数组`matrix`和`memo`，分别用于存储矩阵的维数和已计算过的中间结果。然后，我们定义了一个递归函数`matrixChainOrder`，用于计算矩阵连乘积的最小代价。在这个函数中，我们首先检查备忘录中是否已经计算过该问题的中间结果，如果已经计算过，则直接返回中间结果。否则，我们遍历所有可能的分割点，分别计算左右两部分的最小代价，并加上当前分割点左右两部分的乘积的代价，求得整个问题的最小代价。最后，我们记录计算过的中间结果，并返回最小代价。

在`main`函数中，我们首先读入矩阵的维数，然后用输入的维数初始化`matrix`数组。接着，我们初始化备忘录`memo`，将所有元素都设置为-1。最后，我们调用`matrixChainOrder`函数，输出矩阵连乘积的最小代价。