Implement a dynamic programming solution to identify the least-cost way of performing a chained matrix multiplication. Also implement, to compare the costs, your favorite (or obvious) greedy way of performing chained matrix multiplication.

Problem: Matrix Chain Multiplication (Comparison between DP and Recursive (greedy) approach)

We have so many options to multiply a chain of matrices because matrix multiplication is associative.

Optimal Substructure in the Matrix Chain Multiplication Problem:

Place parenthesis at all possible places, calculate the cost for each placement and return the minimum value. So when we place a set of parentheses, we divide the problem into subproblems of smaller size. Therefore, the problem has optimal substructure property and can be easily solved using recursion.

For example, if the given chain is of 5 matrices (PQRST), then there are 4 ways to place the first set of parenthesis outer side: (P)(QRST), (PQ)(RST), (PQR)(ST) and (PQRS)(T).

Minimum number of multiplication needed to multiply a chain of size k = Minimum of all k-1 placements

Recursive implementation (Optimal Substructure Property):

class { // Matrix has dimension arr[i-1] x arr[i] for i = 1..n static void ChainedMatrixOrder(int arr[], int i, int j) { if (i == j) return 0; int minimum = Integer.MAX_VALUE; //Recursively counting the number of multiplications and storing the min. for (int k=i; k<j; k++) { int count = ChainedMatrixOrder(arr, i, k) + ChainedMatrixOrder(arr, k+1, j) + arr[i-1]*arr[k]*arr[j]; if (count < minimum) minimum = count; } System.out.println("Minimum number of multiplications needed is: "+ min); } public static void main(String args[]) { int input[] = new int[] {1, 2, 3, 4, 3}; int size = input.length; ChainedMatrixOrder(input, 1, size-1); } }  

Output:

Minimum number of multiplications needed is: 30  

Time Complexity: Exponential

Dynamic Programming Approach:

class { // Matrix Ai has dimension arr[i-1] x arr[i] for i = 1..n static void chainedMatrixOrder(int arr[], int n) { int min[][] = new int[n][n]; int i, j, k, len, q; /* min[p,q] = Minimum number of multiplications needed to compute the matrix A[p]A[p+1]...A[q] = A[p...q] where dimension of A[i] is arr[i-1] x arr[i] */ // cost is zero when multiplying one matrix. for (i = 1; i < n; i++) min[i][i] = 0; // len is chain length. for (len=2; len<n; len++) { for (i=1; i<n-len+1; i++) { j = i+len-1; if(j == n) continue; min[i][j] = Integer.MAX_VALUE; for (k=i; k<=j-1; k++) { // q = cost q = min[i][k] + min[k+1][j] + arr[i-1]*arr[k]*arr[j]; if (q < min[i][j]) min[i][j] = q; } } } System.out.println("Minimum number of multiplications neede is: "+ min[1][n-1]); } public static void main(String args[]) { int input[] = new int[] {1, 2, 3, 4}; int size = arr.length; chainedMatrixOrder(input, size) } }

Output:

Minimum number of multiplications needed is: 18  

Time Complexity: O(n3)

Space Complexity: O(n2)