动态规划矩阵连乘c++完整代码

下面是一个简单的动态规划矩阵连乘的 C++ 代码：

#include <iostream>
#include <climits>
using namespace std;

// 矩阵链乘最小代价
int matrixChainOrder(int p[], int n) {
    // m[i][j] 表示从 i 到 j 的矩阵链的最小代价
    int m[n][n];

    // 对角线上的值都为 0，因为单个矩阵的乘法代价为 0
    for (int i = 1; i < n; i++) {
        m[i][i] = 0;
    }

    // L 为矩阵链长度，从小到大计算
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX; // 初始化为最大值

            // 在所有可能的位置上计算最小代价
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                }
            }
        }
    }

    // 返回从第一个矩阵到最后一个矩阵的最小代价
    return m[1][n - 1];
}

int main() {
    int arr[] = {10, 20, 30, 40, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum number of multiplications is " << matrixChainOrder(arr, n) << endl;
    return 0;
}

该代码使用了一个二维数组 m 来存储所有从 i 到 j 的矩阵链的最小代价。它通过对角线逐步向外扩展，按照矩阵链长度从小到大进行计算。在计算每个长度的矩阵链时，它在所有可能的位置上计算最小代价，并将结果存储在数组 m 中。最终，它返回从第一个矩阵到最后一个矩阵的最小代价。