矩阵链乘法

Question

在网站geeksforgeeks上，我发现了矩阵链乘法的任务。

该问题有一个递归解决方案，但我不理解代码。实际上，我对代码中的某一行感到困惑。

首先，这是代码：

#include <stdio.h>
#include <limits.h>

//Matrix Ai has dimension p[i-1] x p[i] for i = 1...n
int MatrixChainOrder(int p[], int i, int j)
{
    if(i == j)
        return 0;
    int k, min = INT_MAX, count;

    for(k=i; k < j; k++) {
        count = MatrixChainOrder(p,i,k) + MatrixChainOrder(p,k+1,j) + p[i-1]*p[k]*p[j];

    if(count < min)
        min = count;
    }

    return min;
}

int main() {

    int arr[] = {1, 2, 3, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, 1, n-1));

    getchar();
    return 0;
}

矩阵如下：A=1x2，B=2x3，C=3x4，D=4x3。

导致我困扰的是以下这行代码：

count = MatrixChainOrder(p,i,k) + MatrixChainOrder(p,k+1,j) + p[i-1]*p[k]*p[j];

在for循环的开始，i = 1和j = 4。因此，p[i-1]*p[k]*p[j]会被计算为p[0]*p[1]*p[4] = 1x2x3，显然是错误的，因为矩阵A只能与B相乘。我运行了代码，似乎什么也没有发生，因为p[i-1]*p[k]*p[j]没有返回结果，同样的问题也出现在i = 2, j = 4的情况下。

请问有人能给我讲解一下吗？如果您能向我解释这段代码中的递归方式以及它的工作原理，我将不胜感激。

- user2965601

---

我在代码片段中没有看到任何C++，所以我冒昧更改了语言标签。 - Some programmer dude

Answer 1

答案在递归中的操作。假设这代表着将ABCD相乘，那么循环迭代中表示通过(A)(BCD)执行此计算。 MatrixChainOrder(p,i,k)计算计算最佳方法来计算(A)，这是一个1x2矩阵，MatrixChainOrder(p,k+1,j)计算计算最佳方法来计算(BCD)，这是一个2x3矩阵。

最后，您感兴趣的术语p[i-1]*p[k]*p[j]是执行(A)和(BCD)的最终乘法的标量乘法次数。

- Degustaf