Matrix Chain Multiplication

Question

On the website geeksforgeeks I came across the task of matrix chain multiplication.

There is a recursive solution for that problem, but I am having trouble understanding the code. Actually, I am having trouble with a certain line of the code.

First of all here is the code:

#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;
}

The matrices are: A=1x2, B=2x3, C=3x4, D=4x3

The line, which is causing me some trouble is

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

At the beginning of the for-loop, i = 1 and j = 4. So, p[i-1]*p[k]*p[j] would evaluate to p[0]*p[1]*p[4] = 1x2x3, which is obviously wrong, because the matrix A can only multiplied with B. I ran the code and nothing seem to be happening here, because there was no result given back for p[i-1]*p[k]*p[j] and also the same issue for the case i = 2, j = 4.

May anyone enlighten me? I would appreciate it, if you explain me the recursion in this code. I mean the way and how it works.

Answer 1

The answer lies in what the recursion is doing. Assuming that this represents multiplying ABCD, then the iteration of the loop with i=1, j=4, k=1 represents performing this calculation by (A)(BCD). MatrixChainOrder(p,i,k) computes the best way to calculate (A), a 1x2 matrix, and MatrixChainOrder(p,k+1,j) computes the best way to calculate (BCD), a 2x3 matrix.

Finally, the term you are interested in p[i-1]*p[k]*p[j] is the number of scalar multiplications to perform the final multiplication of (A) and (BCD).