Algorithm to get the minimum no. of multiplications for matrix chain multiplication in dynamic programming approach.

matrixchaindp.c

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

int matrixChainMul(int arr[],int n){
	int m[n][n];
	int i,j,L,k,q;
	for(i=1;i<n;i++)
		m[i][i] = 0;

	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 = m[i][k] + m[k+1][j] + arr[i-1]*arr[k]*arr[j];
				if(q < m[i][j])
					m[i][j] = q;
			}
		}
	}
	return m[1][n-1];
}

int main(){
	int n,i;
	printf("Enter the no. of matrices: ");
	scanf("%d",&n);
	n++;
	int arr[n];
	printf("Enter the dimensions: ");
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	int size = sizeof(arr)/sizeof(arr[0]);
	printf("\nMiimum no of multiplications is: %d\n",matrixChainMul(arr,size));
	return 0;
}