使用c++实现矩阵连乘

矩阵连乘问题是一个经典的动态规划问题，可以使用动态规划算法解决。动态规划的思路是将问题分解为子问题，并将子问题的解缓存起来，避免重复计算，从而提高算法效率。

假设有n个矩阵A1, A2, ..., An，它们的维度分别为p0xp1, p1xp2, ..., p(n-1)xn，其中p0, p1, ..., pn均为正整数。将这n个矩阵连乘起来可以有多种方式，但不同的方式所需的计算次数不同。设A(i,j)表示第i个矩阵到第j个矩阵的连乘所需的最少计算次数，则有以下递推式：

A(i,j) = min{A(i,k)+A(k+1,j)+p(i-1)p(k)p(j)}，其中i≤k<j

上述递推式的含义是，将矩阵Ai到Aj连乘起来的最少计算次数等于将Ai到Ak和Ak+1到Aj先连乘起来的最少计算次数之和，再加上将这两部分矩阵相乘所需的计算次数p(i-1)p(k)p(j)。

以下是一个使用C++实现矩阵连乘的动态规划算法示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 计算矩阵连乘的最少计算次数
int matrixChainOrder(vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> m(n, vector<int>(n));
    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 minCost = matrixChainOrder(p);
    cout << "矩阵连乘的最少计算次数是：" << minCost << endl;
    return 0;
}

上述代码中，matrixChainOrder函数接受一个整数数组p作为参数，该数组表示n个矩阵的维度，其中p[0]表示第一个矩阵的行数，p[1]表示第一个矩阵的列数，p[1]表示第二个矩阵的行数，以此类推。函数返回矩阵连乘的最少计算次数。在函数内部，m[i][j]表示Ai到Aj连乘的最少计算次数。使用一个二维数组m来缓存子问题的解。最终返回m[0][n-1]即可。