c++用动态规划法实现矩阵连乘代码

下面是使用动态规划法实现矩阵连乘的代码：

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

#define MAX_SIZE 100

/* 自定义矩阵结构体 */
typedef struct Matrix {
    int rows;
    int columns;
} Matrix;

/* 动态规划法求解矩阵连乘所需的最小计算次数 */
int matrixChainOrder(Matrix arr[], int n) {
    int i, j, k, l, q;
    int dp[MAX_SIZE][MAX_SIZE];
    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++) {
                q = dp[i][k] + dp[k + 1][j] + arr[i].rows * arr[k].columns * arr[j].columns;
                if (q < dp[i][j]) {
                    dp[i][j] = q;
                }
            }
        }
    }
    return dp[1][n];
}

int main() {
    int n, i;
    Matrix arr[MAX_SIZE];
    printf("请输入矩阵个数：");
    scanf("%d", &n);
    printf("请输入矩阵的行数和列数，用空格隔开：\n");
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &(arr[i].rows), &(arr[i].columns));
    }
    printf("矩阵连乘所需的最小计算次数为：%d", matrixChainOrder(arr, n));
    return 0;
}

其中，`Matrix` 结构体用于存储矩阵的行数和列数，`matrixChainOrder` 函数用于实现动态规划算法，求解矩阵连乘所需的最小计算次数。主函数中，首先输入矩阵个数和每个矩阵的行数和列数，然后调用 `matrixChainOrder` 函数求解最小计算次数，并输出结果。