Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- int MatrixChainOrder(int arr[],int n){
- int min_mul[n][n]={0,0};
- for(int gap=1;gap<n;gap++){
- for(int i=0,j=gap;j<n;i++,j++){
- int val=INT_MAX,sum=0;
- if(i==0||j==0){
- min_mul[i][j]=min_mul[j][i]=0;
- continue;
- }
- for(int k=i;k<j;k++) {
- sum=min_mul[i][k]+min_mul[k+1][j]+arr[i-1]*arr[k]*arr[j];
- if(sum<val)
- val=sum;
- }
- min_mul[i][j]=min_mul[j][i]=val;
- }
- }
- return min_mul[1][n-1];
- }
- int main(){
- int arr[] = {10,20,30};
- int n = sizeof(arr)/sizeof(arr[0]);
- cout << "Minimum number of multiplications is "
- << MatrixChainOrder(arr,n);
- return 0;
- }
Add Comment
Please, Sign In to add comment