Untitled

 avatar
unknown
plain_text
5 months ago
928 B
3
Indexable
#include <stdio.h>
#include <limits.h>

int MatrixChainOrder(int p[], int n) 
{
int m[n][n]; 
int paren[n][n]; 
int i, j, k, L, q;
  for (i = 0; i<n; i++) 
  {
	m[i][i] = 0; 
	for (j = 0; j<n; j++) 
	{
	paren[i][j] = 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; 
          paren[i][j] = k; 
        }
      }  
    }
  }
  printf("Cost Matrix: \n");
  for (i = 1; i<n; i++) 
  {
	for (j = 1; j<n; j++) 
	{
	   printf("%d\t", m[i][j]);
    }
    printf("\n");
  }
return m[1][n - 1];
}
int main() 
{
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d\n", MatrixChainOrder(arr, size));
return 0;
}
Editor is loading...
Leave a Comment