Matrix Chain Multiplication: An array P is given of n+1 positive integers, p[0],
ID: 3556561 • Letter: M
Question
Matrix Chain Multiplication:
An array P is given of n+1 positive integers, p[0],..,p[n]. This array should be viewed as a representation of the orders of the n matrices. In particular, A1 is a matrix of order p[0] X p[1], and A2 is a matrix of order p[1] X p[2]. In general, for each i in the range 1 <= i < = n, the order of Ai is p[i-1] X p[i].This must be familiar to you from the lecture from matrix chain multiplication. Write a program to find the minimum number of multiplication operations to compute the product A1 X A2 X
Explanation / Answer
#include<stdio.h> #include<limits.h> #include<stdlib.h> int MatrixChainOrder(int p[],int n); int main() { int n,i; scanf("%d",&n); int *p = (int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",&p[i]); printf("%d",MatrixChainOrder(p, n)); return 0; } int MatrixChainOrder(int p[], int n) { //insert code here. int i,j,k,l,q; int **m = (int**)malloc((n+1)*sizeof(int*)); for (i=0;i<=n;i++) m[i] = (int*)malloc((n+1)*sizeof(int)); for (i=0;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; } } } return m[1][n-1]; }