C Program for Matrix Chain Multiplication using Recursion
Two matrices of size m*n and n*p when multiplied, they generate a matrix of size m*p and the number of multiplications performed are m*n*p.
Now, for a given chain of N matrices, the first partition can be done in N-1 ways. For example, sequence of matrices A, B, C and D can be grouped as (A)(BCD), (AB)(CD) or (ABC)(D) in these 3 ways.
So a range [i, j] can be broken into two groups like {[i, i+1], [i+1, j]}, {[i, i+2], [i+2, j]}, . . . , {[i, j-1], [j-1, j]}.
- Each of the groups can be further partitioned into smaller groups and we can find the total required multiplications by solving for each of the groups.
- The minimum number of multiplications among all the first partitions is the required answer.
Step-by-step approach:
- Create a recursive function that takes i and j as parameters that determines the range of a group.
- Iterate from k = i to j to partition the given range into two groups.
- Call the recursive function for these groups.
- Return the minimum value among all the partitions as the required minimum number of multiplications to multiply all the matrices of this group.
- The minimum value returned for the range 0 to N-1 is the required answer.
Below is the implementation of the above approach.
C
// C code to implement the // matrix chain multiplication using recursion#include <limits.h>#include <stdio.h>// Matrix Ai has dimension p[i-1] x p[i] // for i = 1 . . . nint MatrixChainOrder(int p[], int i, int j){ if (i == j) return 0; int k; int min = INT_MAX; int count; // Place parenthesis at different places // between first and last matrix, // recursively calculate count of multiplications // for each parenthesis placement // and return the minimum count for (k = i; k < j; k++) { count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j]; if (count < min) min = count; } // Return minimum count return min;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, 1, N - 1)); getchar(); return 0;} |
Minimum number of multiplications is 30
The time complexity of the solution is exponential
Auxiliary Space: O(1)
C Program for Matrix Chain Multiplication | DP-8
Write a C program for a given dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum.
Examples:
Input: arr[] = {40, 20, 30, 10, 30}
Output: 26000
Explanation: There are 4 matrices of dimensions 40×20, 20×30, 30×10, 10×30.
Let the input 4 matrices be A, B, C, is, and D.
The minimum number of multiplications is obtained by putting parenthesis in the following way (A(BC))D.
The minimum is 20*30*10 + 40*20*10 + 40*10*30Input: arr[] = {1, 2, 3, 4, 3}
Output: 30
Explanation: There are 4 matrices of dimensions 1×2, 2×3, 3×4, 4×3.
Let the input 4 matrices be A, B, C, and D.
The minimum number of multiplications is obtained by putting parenthesis in the following way ((AB)C)D.
The minimum number is 1*2*3 + 1*3*4 + 1*4*3 = 30Input: arr[] = {10, 20, 30}
Output: 6000
Explanation: There are only two matrices of dimensions 10×20 and 20×30.
So there is only one way to multiply the matrices, cost of which is 10*20*30
Contact Us