对于矩阵A1(20*25)、A2(25*5)、A3(5*15

矩阵乘法计算开销最小的表达式

• 矩阵乘法 (m x n) * (n x p) 的成本为 m * n * p。
• 矩阵维度为 A1:20x25, A2:25x5, A3:5x15, A4:15x10, A5:10x20, A6:20x25。
  问题分析
  矩阵乘法的计算开销（成本）指的是进行标量乘法的次数。对于两个矩阵和 的乘法，其成本为。对于多个矩阵的链乘法，总成本是所有子乘法成本的累加，且取决于括号（关联顺序），因为不同的顺序会改变中间结果的维度，从而影响后续乘法的成本。
  

#include <iostream>
#include <climits>  // 用于 INT_MAX，常用于初始化最大值

using namespace std;

// 全局变量定义
int matrix_count;  // 矩阵个数（n），表示需要连乘的矩阵数量
int dimensions[1001];  // 维度数组，dimensions[0]到dimensions[n]，存储每个矩阵的行和列维度
int min_cost[1001][1001];  // min_cost[i][j]: 从矩阵Ai到Aj的最小乘法成本，使用二维数组存储动态规划结果
int split_point[1001][1001];  // split_point[i][j]: Ai到Aj的最优断开位置k，用于后续重建最优路径

/**
 * @brief 动态规划求解矩阵连乘的最小成本
 * 该函数使用自底向上的动态规划方法计算矩阵连乘的最小乘法次数。
 * 它遍历所有可能的矩阵子链长度，并为每个子链找到最优的分割点。
 * 时间复杂度：O(n^3)，空间复杂度：O(n^2)。
 */
void compute_min_cost() {
    // 初始化：单个矩阵链的成本为0
    // 当 i == j 时，只有一个矩阵 Ai，不需要进行乘法，所以成本为 0。
    for (int i = 1; i <= matrix_count; ++i) {
        min_cost[i][i] = 0;
    }
    
    // 外层循环：链长度 len，从2到n
    // len 表示当前正在考虑的矩阵子链的长度，从短链逐步到长链，确保子问题已解决。
    for (int len = 2; len <= matrix_count; ++len) {
        // 内层循环：起始位置 i，从1到 matrix_count - len + 1
        // i 遍历所有可能的子链起始点，确保 j = i + len - 1 不超过矩阵总数。
        for (int i = 1; i <= matrix_count - len + 1; ++i) {
            int j = i + len - 1;  // 结束位置j，计算当前子链的结束索引
            min_cost[i][j] = INT_MAX;  // 初始化为最大值，便于后续求最小值
            
            // 尝试所有可能的断开位置k，从i到j-1
            // k 是将矩阵链 Ai...Aj 分成 (Ai...Ak) 和 (Ak+1...Aj) 的分割点。
            for (int k = i; k < j; ++k) {
                // 计算当前方案的总成本：左子链成本 + 右子链成本 + 连接成本
                // 连接成本为 (Ai...Ak) 和 (Ak+1...Aj) 两个结果矩阵相乘的次数。
                // Ai...Ak 的维度是 dimensions[i-1] x dimensions[k]。
                // Ak+1...Aj 的维度是 dimensions[k] x dimensions[j]。
                int current_cost = min_cost[i][k] + min_cost[k + 1][j] + 
                                   dimensions[i - 1] * dimensions[k] * dimensions[j];
                
                // 如果当前方案的成本更小，则更新最小成本和最优分割点
                if (current_cost < min_cost[i][j]) {
                    min_cost[i][j] = current_cost;  // 更新 min_cost[i][j] 为更小的值
                    split_point[i][j] = k;  // 记录当前最优的断开位置 k
                }
            }
        }
    }
}

/**
 * @brief 递归打印最优括号路径
 * @param i 矩阵链的起始索引（从1开始）
 * @param j 矩阵链的结束索引（到n结束）
 * 该函数利用 split_point 数组，通过递归的方式打印出最优的加括号方式。
 * 例如，对于最优路径 ((A1 A2) A3)，会递归拆分成子路径并添加括号。
 */
void print_optimal_path(int i, int j) {
    // 递归终止条件：当只有一个矩阵时，直接打印其名称
    if (i == j) {
        cout << "A" << i;
        return;
    }
    
    // 打印左括号，开始一个新的子分组
    cout << "(";
    // 递归打印左子链：从 i 到最优断开位置 split_point[i][j]
    print_optimal_path(i, split_point[i][j]);
    // 递归打印右子链：从 split_point[i][j]+1 到 j
    print_optimal_path(split_point[i][j] + 1, j);
    // 打印右括号，结束当前子分组
    cout << ")";
}

int main() {
    // 输入矩阵个数
    // 提示用户输入矩阵的数量 n
    cout << "请输入矩阵个数n: ";
    cin >> matrix_count;
    
    // 输入维度数组
    // 提示用户输入 n+1 个维度值，这些值定义了每个矩阵的行和列
    cout << "请输入n+1个维度值 (p0, p1, ..., pn): ";
    for (int i = 0; i <= matrix_count; ++i) {
        cin >> dimensions[i];
    }
    
    // 计算最小成本
    // 调用动态规划函数来填充 min_cost 和 split_point 数组
    compute_min_cost();
    
    // 输出最小乘法次数
    // min_cost[1][matrix_count] 存储了整个矩阵链的最小成本
    cout << "最小乘法次数: " << min_cost[1][matrix_count] << endl;
    
    // 输出最优括号方式
    // 调用递归函数打印最优的加括号表达式
    cout << "最优括号方式: ";
    print_optimal_path(1, matrix_count);
    cout << endl;
    
    return 0;
}

给定矩阵维度：

• A1: 20×25
• A2: 25×5
• A3: 5×15
• A4: 15×10
• A5: 10×20
• A6: 20×25

对应维度数组为 [20, 25, 5, 15, 10, 20, 25]。以下逐个选项计算总成本（假设分组内无内部括号时从左到右关联）。

选项A: (A1A2)(((A3A4)A5)A6)

1. A1 × A2: 20×25×5 = 2500（结果: 20×5）
2. A3 × A4: 5×15×10 = 750（结果: 5×10）
3. (A3A4) × A5: 5×10×20 = 1000（结果: 5×20）
4. ((A3A4)A5) × A6: 5×20×25 = 2500（结果: 5×25）
5. (A1A2) × (((A3A4)A5)A6): 20×5×25 = 2500（结果: 20×25）

总成本: 2500 + 750 + 1000 + 2500 + 2500 = 9250

选项B: (A1A2A3)((A4A5)A6)
假设 (A1A2A3) 为 ((A1A2)A3)。

1. A1 × A2: 20×25×5 = 2500（结果: 20×5）
2. (A1A2) × A3: 20×5×15 = 1500（结果: 20×15）
3. A4 × A5: 15×10×20 = 3000（结果: 15×20）
4. (A4A5) × A6: 15×20×25 = 7500（结果: 15×25）
5. ((A1A2)A3) × ((A4A5)A6): 20×15×25 = 7500（结果: 20×25）

总成本: 2500 + 1500 + 3000 + 7500 + 7500 = 22000

选项C: (((A1((A2A3)A4))A5)A6)

1. A2 × A3: 25×5×15 = 1875（结果: 25×15）
2. (A2A3) × A4: 25×15×10 = 3750（结果: 25×10）
3. A1 × ((A2A3)A4): 20×25×10 = 5000（结果: 20×10）
4. (A1((A2A3)A4)) × A5: 20×10×20 = 4000（结果: 20×20）
5. ((A1((A2A3)A4))A5) × A6: 20×20×25 = 10000（结果: 20×25）

总成本: 1875 + 3750 + 5000 + 4000 + 10000 = 24625

选项D: (A1A2)((A3(A4A5))A6)

1. A1 × A2: 20×25×5 = 2500（结果: 20×5）
2. A4 × A5: 15×10×20 = 3000（结果: 15×20）
3. A3 × (A4A5): 5×15×20 = 1500（结果: 5×20）
4. (A3(A4A5)) × A6: 5×20×25 = 2500（结果: 5×25）
5. (A1A2) × ((A3(A4A5))A6): 20×5×25 = 2500（结果: 20×25）

总成本: 2500 + 3000 + 1500 + 2500 + 2500 = 12000

比较

• A: 9250
• B: 22000
• C: 24625
• D: 12000

为了确定矩阵链乘法中计算开销最小的选项，需要计算每个选项的乘法次数（即标量乘法次数）。矩阵乘法的开销取决于矩阵的维度，两个矩阵 Am×nAm×n 和 Bn×pBn×p 相乘的开销为 m×n×pm×n×p。

给定矩阵维度：

• A1: 20×2520×25

• A2: 25×525×5

• A3: 5×155×15

• A4: 15×1015×10

• A5: 10×2010×20

• A6: 20×2520×25

选项 A: (A1A2)(((A3A4)A5)A6)(A1A2)(((A3A4)A5)A6)

计算步骤及开销：

1. 计算 A1A2A1A2: 20×25×5=250020×25×5=2500，结果矩阵 20×520×5

2. 计算 A3A4A3A4: 5×15×10=7505×15×10=750，结果矩阵 5×105×10

3. 计算 (A3A4)A5(A3A4)A5: 5×10×20=10005×10×20=1000，结果矩阵 5×205×20

4. 计算 ((A3A4)A5)A6((A3A4)A5)A6: 5×20×25=25005×20×25=2500，结果矩阵 5×255×25

5. 计算 (A1A2)×(((A3A4)A5)A6)(A1A2)×(((A3A4)A5)A6): 20×5×25=250020×5×25=2500，结果矩阵 20×2520×25

总开销 = 2500+750+1000+2500+2500=92502500+750+1000+2500+2500=9250

选项 B: (A1A2A3)((A4A5)A6)(A1A2A3)((A4A5)A6)

选项 B 中的 (A1A2A3)(A1A2A3) 未指定括号顺序，需考虑两种可能：

• 情况 1: ((A1A2)A3)((A1A2)A3)

  1. 计算 A1A2A1A2: 20×25×5=250020×25×5=2500，结果矩阵 20×520×5

  2. 计算 (A1A2)A3(A1A2)A3: 20×5×15=150020×5×15=1500，结果矩阵 20×1520×15

  3. 计算 A4A5A4A5: 15×10×20=300015×10×20=3000，结果矩阵 15×2015×20

  4. 计算 (A4A5)A6(A4A5)A6: 15×20×25=750015×20×25=7500，结果矩阵 15×2515×25

  5. 计算 ((A1A2)A3)×((A4A5)A6)((A1A2)A3)×((A4A5)A6): 20×15×25=750020×15×25=7500，结果矩阵 20×2520×25

  总开销 = 2500+1500+3000+7500+7500=220002500+1500+3000+7500+7500=22000

• 情况 2: (A1(A2A3))(A1(A2A3))

  1. 计算 A2A3A2A3: 25×5×15=187525×5×15=1875，结果矩阵 25×1525×15

  2. 计算 A1×(A2A3)A1×(A2A3): 20×25×15=750020×25×15=7500，结果矩阵 20×1520×15

  3. 计算 A4A5A4A5: 15×10×20=300015×10×20=3000，结果矩阵 15×2015×20

  4. 计算 (A4A5)A6(A4A5)A6: 15×20×25=750015×20×25=7500，结果矩阵 15×2515×25

  5. 计算 (A1(A2A3))×((A4A5)A6)(A1(A2A3))×((A4A5)A6): 20×15×25=750020×15×25=7500，结果矩阵 20×2520×25

  总开销 = 1875+7500+3000+7500+7500=273751875+7500+3000+7500+7500=27375

选项 B 的最小开销为 22000（对应 ((A1A2)A3)((A1A2)A3)）。

选项 C: (((A1((A2A3)A4))A5)A6)(((A1((A2A3)A4))A5)A6)

计算步骤及开销：

1. 计算 A2A3A2A3: 25×5×15=187525×5×15=1875，结果矩阵 25×1525×15

2. 计算 (A2A3)A4(A2A3)A4: 25×15×10=375025×15×10=3750，结果矩阵 25×1025×10

3. 计算 A1×((A2A3)A4)A1×((A2A3)A4): 20×25×10=500020×25×10=5000，结果矩阵 20×1020×10

4. 计算 (A1((A2A3)A4))A5(A1((A2A3)A4))A5: 20×10×20=400020×10×20=4000，结果矩阵 20×2020×20

5. 计算 (((A1((A2A3)A4))A5)A6(((A1((A2A3)A4))A5)A6: 20×20×25=1000020×20×25=10000，结果矩阵 20×2520×25

总开销 = 1875+3750+5000+4000+10000=246251875+3750+5000+4000+10000=24625

选项 D: (A1A2)((A3(A4A5))A6)(A1A2)((A3(A4A5))A6)

计算步骤及开销：

1. 计算 A1A2A1A2: 20×25×5=250020×25×5=2500，结果矩阵 20×520×5

2. 计算 A4A5A4A5: 15×10×20=300015×10×20=3000，结果矩阵 15×2015×20

3. 计算 A3×(A4A5)A3×(A4A5): 5×15×20=15005×15×20=1500，结果矩阵 5×205×20

4. 计算 (A3(A4A5))A6(A3(A4A5))A6: 5×20×25=25005×20×25=2500，结果矩阵 5×255×25

5. 计算 (A1A2)×((A3(A4A5))A6)(A1A2)×((A3(A4A5))A6): 20×5×25=250020×5×25=2500，结果矩阵 20×2520×25

总开销 = 2500+3000+1500+2500+2500=120002500+3000+1500+2500+2500=12000

比较各选项开销

• 选项 A: 9250

• 选项 B: 22000（最小可能）

• 选项 C: 24625

• 选项 D: 12000

最小开销为 9250，对应选项 A。此外，通过动态规划计算整个矩阵链的最小开销也为 9250，与选项 A 一致。

因此，计算开销最小的是 A。