c - 矩阵链乘法

Question

在网站上geeksforgeeks我遇到了matrix chain multiplication的任务.

该问题有一个递归解决方案，但我无法理解代码。实际上，我在执行某行代码时遇到了问题。

首先是代码:

#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< 的情况也存在同样的问题.

有人可以启发我吗？如果您向我解释这段代码中的递归，我将不胜感激。我的意思是它的工作方式和方式。

Answer 1

答案在于递归正在做什么。假设这代表乘法ABCD ，然后用 i=1, j=4, k=1 进行循环迭代表示通过 (A)(BCD) 执行此计算。 MatrixChainOrder(p,i,k)计算(A)的最佳计算方式，一个1x2矩阵，和MatrixChainOrder(p,k+1,j)计算(BCD)的最佳计算方式，一个2x3矩阵。

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