矩阵链乘法为何采用三重循环？循环结构设计逻辑解析

嘿，我完全懂你在矩阵链乘法问题里对着这段三重循环犯懵的感觉——当初我第一次啃这段代码时，也盯着j = i+L-1和i的循环条件琢磨了好半天！咱们一步步拆解，你就能搞明白这类只填充上三角矩阵的动态规划循环到底是怎么设计出来的。

首先先明确基础定义：假设我们有n个矩阵A₁, A₂, ..., Aₙ，其中Aᵢ的维度是p[i-1] × p[i]。二维数组m[i][j]用来存储计算矩阵链Aᵢ到Aⱼ的最小乘法次数。

1. 外层循环：L的含义 #

外层循环的L代表的是当前处理的矩阵链的长度。比如：

• L=2时，我们处理的是两个矩阵相乘的情况（比如A₁A₂、A₂A₃这类）；
• L=3时，处理三个矩阵连乘的链（A₁A₂A₃、A₂A₃A₄）；
• 直到L=n时，才会处理整个完整的矩阵链A₁到Aₙ。

为什么从L=2开始？因为单个矩阵（L=1）的乘法次数是0，根本不需要计算，所以直接从长度为2的链开始处理。

2. 中层循环：i的范围和j的推导 #

• i是当前矩阵链的起始下标，j是对应的结束下标。
• 当链的长度是L时，从i开始数L个矩阵，结束下标自然就是i + L - 1——举个例子：i=1，L=2，j=1+2-1=2，对应矩阵链A₁A₂；i=2，L=3，j=2+3-1=4，对应A₂A₃A₄，是不是完全符合直觉？

那i < n-L+1这个循环条件怎么来的？很简单，我们要保证结束下标j不超过n（毕竟我们的矩阵最多到Aₙ），也就是i + L - 1 ≤ n，解这个不等式就能得到i ≤ n - L + 1，所以循环里用i < n-L+1（这里代码里i从1开始，这个条件刚好能让j的最大值为n，不会越界）。比如n=5，L=3，n-L+1=5-3+1=3，所以i可以取1、2、3，对应的j分别是3、4、5，刚好覆盖所有长度为3的矩阵链，一点都不会超出范围。

3. 为什么只填充上三角矩阵？ #

当i > j时，m[i][j]没有任何意义——总不能从下标更大的矩阵开始，往小的矩阵方向连乘吧？而当i = j时，m[i][j] = 0（单个矩阵不需要做乘法）。所以我们只需要填充i ≤ j的区域，也就是矩阵的上三角部分。

而且按照L从小到大的顺序遍历，我们是先计算短链的最小代价，再用短链的结果去推导长链的代价——这正是动态规划的核心：子问题的最优解必须在父问题之前被计算出来，这样我们用到子问题结果的时候，它已经是正确的最小值了。

加了注释的代码 #

for (int L=2; L<n; L++){ 
    // L：当前处理的矩阵链长度，从2开始（单个矩阵无需计算）
    for (int i=1; i<n-L+1; i++) { 
        // i：当前链的起始下标，保证结束下标j不会超过n
        int j = i+L-1; // 由起始下标+链长-1，得到链的结束下标
        m[i][j] = INT_MAX; // 先把最小代价初始化为无穷大
        for (int k=i; k<=j-1; k++) { 
            // k：尝试所有可能的分割点，把链拆成A_i~A_k 和 A_{k+1}~A_j两部分
            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; // 更新为更小的代价
                bracket[i][j] = k; // 记录下这个最优分割点
            }
        }
    } 
}

这类循环的通用逻辑 #

其实不止矩阵链乘法，很多类似的区间型动态规划问题（比如最长回文子串、石子合并）都会用到这种循环设计：

• 外层循环控制子问题的规模（比如链长、区间长度），从小到大遍历；
• 中层循环控制子问题的起始位置，通过规模推导结束位置，确保不越界；
• 内层循环遍历所有可能的分割/转移方式，找到子问题的最优组合。

内容的提问来源于stack exchange，提问作者user9818569