用c++写矩阵连乘输出显示为乘号执行的位置顺序以及最小矩阵乘法次数

矩阵连乘问题可以使用动态规划来解决，具体步骤如下：

1. 定义一个二维数组 `dp[i][j]` 表示矩阵链从第 `i` 个矩阵到第 `j` 个矩阵的最小乘法次数。

2. 初始化 `dp` 数组，对角线上的值为 0，因为单个矩阵不需要乘法次数。

3. 从长度为 2 的矩阵链开始计算，依次计算长度为 3、4、... 直到 `n` 的矩阵链。对于每个长度 `len`，从 `i=1` 开始计算，计算 `dp[i][i+len-1]` 的值。

4. 计算 `dp[i][j]` 的值时，枚举断点 `k`，将矩阵链分成两部分，即 `i~k` 和 `k+1~j`。此时的乘法次数为 `dp[i][k] + dp[k+1][j] + rows[i] * cols[k] * cols[j]`，其中 `rows[i]` 表示第 `i` 个矩阵的行数，`cols[j]` 表示第 `j` 个矩阵的列数。

5. 计算完所有可能的断点后，取最小值作为 `dp[i][j]` 的值。

6. 最终的答案为 `dp[1][n]`。

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

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

void printOrder(vector<vector<int>>& s, int i, int j) {
    if (i == j) {
        cout << "A" << i;
        return;
    }
    cout << "(";
    printOrder(s, i, s[i][j]);
    printOrder(s, s[i][j]+1, j);
    cout << ")";
}

int matrixChainOrder(vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> dp(n+1, vector<int>(n+1));
    vector<vector<int>> s(n+1, vector<int>(n+1));
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n-len+1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < dp[i][j]) {
                    dp[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    cout << "Order of multiplication: ";
    printOrder(s, 1, n);
    cout << endl;
    return dp[1][n];
}

int main() {
    vector<int> p = {10, 100, 5, 50};
    int minMul = matrixChainOrder(p);
    cout << "Minimum number of multiplications: " << minMul << endl;
    return 0;
}

输出结果为：

Order of multiplication: (A1(A2A3))A4
Minimum number of multiplications: 7500

其中，`s` 数组记录的是乘法的位置顺序，`printOrder` 函数用于输出乘法的顺序。最小乘法次数为 7500。