algorithm - 为什么我们在矩阵链乘法中使用三个循环？

Question

我正在学习动态规划。我被困在这个问题上 Matrix Chain Multiplication。我理解三个循环的需要。但是如何想出这些安排，如 j = i+L-1 和 i 的测试条件。 还有其他一些具有类似解决方案的 DP 问题，我注意到这些循环仅用于填充上三角矩阵。我想知道为什么我们要这样写循环？

for (int L=2; L<n; L++){
    for (int i=1; i<n-L+1; i++)
    {
        int j = i+L-1; // Why ?
        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;
            bracket[i][j] = k;
            }
        }
    }
}

Answer 1

L 是 Chain 的长度。 我是行号。 j 是列号。 k是中间乘法。