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