使用C++用动态规划编写矩阵连乘

矩阵连乘问题是一个经典的动态规划问题。假设有n个矩阵，它们的维度分别为d0×d1、d1×d2……dn-1×dn，现在要将它们相乘，求出最少需要进行多少次乘法运算。

下面是使用C++实现矩阵连乘问题的代码：

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

int matrixChainOrder(vector<int>& dims) {
    int n = dims.size() - 1;
    vector<vector<int>> dp(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;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

int main() {
    vector<int> dims = {10, 30, 5, 60};
    int minCost = matrixChainOrder(dims);
    cout << "Minimum cost of matrix multiplication is: " << minCost << endl;
    return 0;
}

在这个代码中，我们使用了一个二维数组`dp`来存储各种长度的矩阵连乘的最小花费。我们首先初始化所有长度为1的矩阵的花费为0，然后逐步增加矩阵的长度，直到整个问题的规模。

在每次迭代中，我们遍历所有可能的断点，计算出当前断点下的矩阵链的花费，并更新`dp`数组。最终，`dp[0][n-1]`就是整个问题的最小花费。

这个问题的时间复杂度为O(n^3)，其中n是矩阵的个数。