c++用动态规划实现矩阵连乘输出最优断点次序

矩阵连乘问题的动态规划算法分为三个步骤：
1. 状态定义：设 $m[i][j]$ 表示第 $i$ 个矩阵到第 $j$ 个矩阵的最小计算次数，$s[i][j]$ 表示第 $i$ 个矩阵到第 $j$ 个矩阵的最优断点。
2. 状态转移方程：对于 $i\leq k<j$，有 $m[i][j]=\min(m[i][k]+m[k+1][j]+p_{i-1}p_kp_j)$，其中 $p_i$ 表示第 $i$ 个矩阵的行数，$p_{i+1}$ 表示第 $i$ 个矩阵的列数。
3. 求解最优解：根据 $s[i][j]$ 数组输出断点序列。

下面是C++代码实现：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

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

void matrixChainOrder(vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> m(n+1, vector<int>(n+1, 0));
    vector<vector<int>> s(n+1, vector<int>(n+1, 0));

    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n-l+1; i++) {
            int j = i + l - 1;
            m[i][j] = numeric_limits<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;
                    s[i][j] = k;
                }
            }
        }
    }

    cout << "最小计算次数：" << m[1][n] << endl;
    cout << "最优断点序列：";
    printOptimalParens(s, 1, n);
    cout << endl;
}

int main() {
    vector<int> p = {30, 35, 15, 5, 10, 20, 25};
    matrixChainOrder(p);
    return 0;
}

输出结果如下：

最小计算次数：15125
最优断点序列：((A1(A2A3))(A4A5))