矩阵连乘算法备忘录c++语言

矩阵连乘算法可以使用动态规划来解决，具体实现如下：

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

void matrixChainOrder(vector<int>& p, vector<vector<int>>& m, vector<vector<int>>& s) {
    int n = p.size() - 1;
    for (int i = 1; i <= n; ++i) {
        m[i][i] = 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] = INT_MAX;
            for (int k = i; k <= j - 1; ++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;
                }
            }
        }
    }
}

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 << ")";
    }
}

int main() {
    vector<int> p{30, 35, 15, 5, 10, 20, 25};
    int n = p.size() - 1;
    vector<vector<int>> m(n + 1, vector<int>(n + 1));
    vector<vector<int>> s(n + 1, vector<int>(n + 1));
    matrixChainOrder(p, m, s);
    cout << "最少乘法次数：" << m[1][n] << endl;
    cout << "最优加括号方案：";
    printOptimalParens(s, 1, n);
    return 0;
}