C Program for Matrix Chain Multiplication using Dynamic Programming (Memoization)
Step-by-step approach:
- Build a matrix dp[][] of size N*N for memoization purposes.
- Use the same recursive call as done in the above approach:
- When we find a range (i, j) for which the value is already calculated, return the minimum value for that range (i.e., dp[i][j]).
- Otherwise, perform the recursive calls as mentioned earlier.
- The value stored at dp[0][N-1] is the required answer.
Below is the implementation of the above approach:
C
#include <stdio.h>#include <limits.h>int dp[100][100];// Function for matrix chain multiplicationint matrixChainMemoised(int p[], int i, int j) { if (i == j) { return 0; } if (dp[i][j] != -1) { return dp[i][j]; } dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { dp[i][j] = (dp[i][j] < (matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j) + p[i - 1] * p[k] * p[j])) ? dp[i][j] : (matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j) + p[i - 1] * p[k] * p[j]); } return dp[i][j];}int MatrixChainOrder(int p[], int n) { int i = 1, j = n - 1; return matrixChainMemoised(p, i, j);}int main() { int arr[] = {1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); // Corrected this line for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { dp[i][j] = -1; } } printf("Minimum number of multiplications is %d\n", MatrixChainOrder(arr, n)); return 0;} |
Minimum number of multiplications is 18
Time Complexity: O(N3 )
Auxiliary Space: O(N2) ignoring recursion stack space
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