矩阵链乘法【东北大学oj数据结构10-2】C++

矩阵链乘法问题的目标是找到最有效的方法来乘以给定的 n 个矩阵 M1,M2,M3,...,Mn。
编写一个程序，读取 Mi 的维度，并找到最小标量乘法以计算最大链链乘法 M1M2...Mn。

输入
在第一行中，给出了一个整数 n。 在接下来的 n 行中，矩阵 Mi (i=1...n) 的维度由两个整数 r 和 c 给出，分别表示 Mi 的行数和列数。

输出
在一行中打印最小数量的标量乘法。

约束
1≤n≤100
1≤r,c≤100

输入样例

6
30 35
35 15
15 5
5 10
10 20
20 25

输出样例

 15125

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    //matrices直接存储一对数据
    vector<pair<int, int>> matrices(n);
    for (int i = 0; i < n; ++i) {
        cin >> matrices[i].first >> matrices[i].second;
    }

    // 二维数组dp[i][j] 表示计算矩阵 Mi...Mj 所需的最小乘法次数
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 0;
    }

    //计算维度为 m x n 的矩阵 A 和 n x p 的矩阵 B 的乘积，需要 m * n * p 次标量乘法
    //矩阵A (Mi 到 Mk 的乘积) 的维度
    //行数等于 Mi 的行数 (ri-1，用 matrices[i].first 表示)
    //列数等于 Mk 的列数 (ck，用 matrices[k].second 表示)
    //矩阵A的维度为 matrices[i].first x matrices[k].second

    //矩阵B (Mk+1 到 Mj 的乘积) 的维度
    //行数等于 Mk+1 的行数，但由于矩阵是链式相乘，Mk+1的行数会等于Mk的列数
    //因此Mk+1的行数等于ck，即matrices[k].second
    //列数等于 Mj 的列数 (cj，用 matrices[j].second 表示)
    //矩阵B的维度为matrices[k].second x matrices[j].second
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            dp[i][j] = 1e9; // 初始化为一个很大的值
            //循环遍历可能的分割点 k
            for (int k = i; k < j; ++k) {
                int cost = dp[i][k] + dp[k + 1][j] +
                           matrices[i].first * matrices[k].second * matrices[j].second;
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }


    cout << dp[0][n - 1] << endl;

    return 0;
}