C Program for Matrix Chain Multiplication using Dynamic Programming (Tabulation)
In iterative approach, we initially need to find the number of multiplications required to multiply two adjacent matrices. We can use these values to find the minimum multiplication required for matrices in a range of length 3 and further use those values for ranges with higher lengths.
Build on the answer in this manner till the range becomes [0, N-1].
Step-by-step approach:
- Iterate from l = 2 to N-1 which denotes the length of the range:
- Iterate from i = 0 to N-1:
- Find the right end of the range (j) having l matrices.
- Iterate from k = i+1 to j which denotes the point of partition.
- Multiply the matrices in range (i, k) and (k, j).
- This will create two matrices with dimensions arr[i-1]*arr[k] and arr[k]*arr[j].
- The number of multiplications to be performed to multiply these two matrices (say X) are arr[i-1]*arr[k]*arr[j].
- The total number of multiplications is dp[i][k]+ dp[k+1][j] + X.
- Iterate from i = 0 to N-1:
- The value stored at dp[1][N-1] is the required answer.
Below is the implementation of the above approach:
C
// See the Cormen book for details of the following // algorithm #include <limits.h> #include <stdio.h> // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n int MatrixChainOrder( int p[], int n) { /* For simplicity of the program, one extra row and one extra column are allocated in m[][]. 0th row and 0th column of m[][] are not used */ 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]; } // Driver code int main() { int arr[] = { 1, 2, 3, 4 }; int size = sizeof (arr) / sizeof (arr[0]); printf ( "Minimum number of multiplications is %d " , MatrixChainOrder(arr, size)); getchar (); return 0; } |
Minimum number of multiplications is 18
Time Complexity: O(N3 )
Auxiliary Space: O(N2)
Please refer complete article on Matrix Chain Multiplication | DP-8 for more details!
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