Implement a dynamic programming solution to identify the lea

Implement a dynamic programming solution to identify the least-cost way of performing chained matrix multiplication. Compare your cost with your favorite (or obvious) greedy way of performing chained matrix multiplication.

Solution

Greedy method

==========================================

#include<stdio.h>
#include<limits.h>

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChain(int m[], int i, int j)
{
   if(i == j)
       return 0;
   int k;
   int min = INT_MAX;
   int count;

  
   for (k = i; k <j; k++)
   {
       count = MatrixChain(m, i, k) +
               MatrixChain(m, k+1, j) +
               m[i-1]*m[k]*m[j];

       if (count < min)
           min = count;
   }

   // Return minimum count
   return min;
}

int main()
{
   int arr[] = {1, 2, 3, 4, 3};
   int n = sizeof(arr)/sizeof(arr[0]);

   printf(\"Minimum number of multiplications is %d \",
                       MatrixChain(arr, 1, n-1));

   return 0;
}

Output:

==================================================================

dynamic Programming

#include<stdio.h>
#include<limits.h>

int MatrixChain(int p[], int n)
{

  
   int m[n][n];

   int i, j, k, L, q;

   /* m[i,j] = Minimum number of scalar multiplications needed
   to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
   dimension of A[i] is p[i-1] x p[i] */

   // cost is zero when multiplying one matrix.
   for (i=1; i<n; i++)
       m[i][i] = 0;

   // L is chain length.
   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 = cost/scalar multiplications
               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];
}

int main()
{
   int a[] = {1, 2, 3, 4};
   int size = sizeof(a)/sizeof(a[0]);

   printf(\"Minimum number of multiplications is %d \",
                   MatrixChain(a, size));

   return 0;
}

OutPut: