matrix_mul_order.cpp

// See the Cormen book for details of the 
// following algorithm 
#include<bits/stdc++.h> 
using namespace std; 
int b[10][10]; 
void order(int arr[10],int i,int j,char & name)
{
	if(i==j)
	{	cout<<name++ ;
		return;
	}
		cout<<"( ";
		order(arr,i,b[i][j],name);
		order(arr,b[i][j]+1,j,name);
		cout<<" )";
}
void MatrixChainOrder(int p[], int n) 
{ 
	int m[n][n];

	int i, j, k, L, 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] + 
					p[i - 1] * p[k] * p[j]; 
				if (q < m[i][j]) 
					{
					m[i][j] = q; 
					b[i][j] = k;
					}
			} 
		} 
	} 
	cout<<" Optimal Parenthesization is :\n";
	char name='A';
	order(p,1,n-1,name);
	cout<<"\nEfficient cost is "<< m[1][n - 1]; 
}  
int main() 
{ 
	int arr[] = {1, 2, 3, 4,5}; 
	int size = sizeof(arr) / sizeof(arr[0]); 

	 MatrixChainOrder(arr, size);
	
	return 0; 
}