1用c++实现矩阵连乘

矩阵连乘问题是一个经典的动态规划问题，它的目标是在最小化矩阵乘法的总代价的同时，确定一种矩阵乘法的执行顺序。假设有n个矩阵A1到An，它们的维度分别为d[0] * d[1]，d[1] * d[2]，……，d[n-1] * d[n]，则矩阵乘法的总代价为(n-1)个子问题的代价之和，即：

m[i][j] = min{m[i][k] + m[k+1][j] + d[i-1]*d[k]*d[j]}(i <= k < j)

其中，m[i][j]表示从Ai到Aj进行矩阵乘法的最小代价。

下面是C++实现矩阵连乘的代码：

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int matrixChainOrder(vector<int> p) {
    int n = p.size() - 1;
    vector<vector<int>> m(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                }
            }
        }
    }
    return m[0][n-1];
}

int main() {
    vector<int> p{10, 20, 30, 40, 30};
    int result = matrixChainOrder(p);
    cout << "Minimum number of multiplications is " << result << endl;
    return 0;
}

上述代码中，vector<int> p表示矩阵的维度，n表示矩阵的个数，m[i][j]表示从Ai到Aj进行矩阵乘法的最小代价，len表示矩阵链长度，k表示分割点。