c - 使用 DP 的链式矩阵乘法的解释？

Question

我无法理解算法书中给出的优化链式矩阵乘法(使用 DP)代码示例。

int MatrixChainOrder(int p[], int n)
{

    /* For simplicity of the program, one extra row and one extra column are
       allocated in m[][].  0th row and 0th column of m[][] are not used */
    int m[n][n];

    int i, j, k, L, q;

    /* m[i,j] = Minimum number of scalar multiplications needed to compute
       the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
       p[i-1] x p[i] */

    // cost is zero when multiplying one matrix.
    for (i = 1; i < n; i++)
        m[i][i] = 0;

    // L is chain length.  
    for (L=2; L<n; L++)   
    {
        for (i=1; i<=n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            for (k=i; k<=j-1; k++)
            {
                // q = cost/scalar multiplications
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }

    return m[1][n-1];
}

为什么第一个循环从 2 开始？为什么 j 设置为 i+L-1 而 i 设置为 n-L+1 ？

我明白了递归关系，但不明白为什么循环是这样设置的？

编辑:

DP后面的括号顺序怎么获取？

Answer 1

自下而上，即 DP 我们首先尝试解决最小的可能情况(我们解决每个最小的情况)。现在，当我们查看递归时(m[i,j] 表示从 i , j.. 到括号的成本)

我们可以看到最小可能的解决方案(任何其他更大的子问题都需要它)的长度小于我们需要解决的长度...对于 P(n) 。我们需要用括号括起长度小于 n 的表达式的所有成本。这导致我们纵向解决问题......(注意外循环中的 l 表示我们试图优化其成本的段的长度)

现在我们首先解决所有长度为 1 的子问题，即总是 0(不需要乘法)...

现在你的问题 L=2 -> L=n我们改变长度从 2 到 n 只是为了按顺序解决子问题...

i 是所有子区间的起点，因此它们可以是长度为 l 的区间的开始。

自然j代表子区间的终点->i+l-1就是子区间的终点(因为我们知道起点和长度就可以算出子区间的终点)