C Program for Matrix Chain Multiplication

C Program for Matrix Chain Multiplication : Sequence of matrices, find the most efficient way to multiply these matrices together.

C Program for Matrix Chain Multiplication

#include<bits/stdc++.h> 
using namespace std; 
int MatrixChainOrder(int p[], int i, int j) 
{ 
	if(i == j) 
		return 0; 
	int k; 
	int min = INT_MAX; 
	int 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]); 

	cout << "Minimum number of multiplications is "
		<< MatrixChainOrder(arr, 1, n - 1); 
} 

Output of Program

Minimum number of multiplications is 30