jain12

matrix chain multiplication

Jun 6th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. int MatrixChainOrder(int arr[],int n){
  4.  int min_mul[n][n]={0,0};
  5.  for(int gap=1;gap<n;gap++){
  6.     for(int i=0,j=gap;j<n;i++,j++){
  7.       int val=INT_MAX,sum=0;
  8.       if(i==0||j==0){
  9.         min_mul[i][j]=min_mul[j][i]=0;
  10.         continue;
  11.         }
  12.       for(int k=i;k<j;k++) {
  13.         sum=min_mul[i][k]+min_mul[k+1][j]+arr[i-1]*arr[k]*arr[j];
  14.         if(sum<val)
  15.             val=sum;
  16.         }
  17.       min_mul[i][j]=min_mul[j][i]=val;
  18.       }
  19.     }
  20.     return min_mul[1][n-1];
  21.   }
  22.  
  23. int main(){
  24.   int arr[] = {10,20,30};
  25.   int n = sizeof(arr)/sizeof(arr[0]);
  26.   cout << "Minimum number of multiplications is "
  27.        << MatrixChainOrder(arr,n);
  28.   return 0;
  29.   }
Add Comment
Please, Sign In to add comment