Matrix Chain Multiplication in DSA C - Build from Scratch

Matrix Chain Multiplication

📖 Scenario: You work in a software company that optimizes mathematical computations. One common task is to multiply a chain of matrices in the most efficient way to save time and resources.Matrix Chain Multiplication helps find the best order to multiply matrices so that the total number of scalar multiplications is minimized.

🎯 Goal: You will write a program in C that uses dynamic programming to find the minimum number of multiplications needed to multiply a chain of matrices.The program will take the dimensions of matrices and output the minimum cost.

📋 What You'll Learn

Create an integer array dims with the exact values {40, 20, 30, 10, 30}

Create an integer variable n that stores the number of matrices (length of dims - 1)

Create a 2D integer array m of size n x n to store minimum multiplication costs

Implement the matrix chain multiplication dynamic programming logic using nested loops

Print the minimum multiplication cost stored in m[0][n-1]

💡 Why This Matters

🌍 Real World

Matrix chain multiplication is used in computer graphics, scientific computing, and database query optimization to speed up matrix operations.

💼 Career

Understanding dynamic programming and optimization techniques like matrix chain multiplication is valuable for software engineers working on performance-critical applications.

1

Create the dimensions array

Create an integer array called dims with the exact values {40, 20, 30, 10, 30}.

DSA C

# Your code here

Hint

The array dims holds the dimensions of 4 matrices: A1 is 40x20, A2 is 20x30, A3 is 30x10, A4 is 10x30.

2

Set the number of matrices and declare the cost matrix

Create an integer variable called n that stores the number of matrices (which is the length of dims minus 1). Then declare a 2D integer array called m of size n by n to store minimum multiplication costs.

DSA C

int dims[] = {40, 20, 30, 10, 30};
# Your code here

Hint

Use sizeof(dims) / sizeof(dims[0]) - 1 to get the number of matrices.

Declare m as a 2D array to hold costs.

3

Implement the matrix chain multiplication logic

Initialize the diagonal of m with zeros using a for loop with variable i. Then use nested for loops with variables L, i, and k to compute minimum multiplication costs. Use variables j and q inside the loops. Update m[i][j] with the minimum cost found.

DSA C

int dims[] = {40, 20, 30, 10, 30};
int n = sizeof(dims) / sizeof(dims[0]) - 1;
int m[n][n];
// Your code here

Hint

Set the diagonal of m to zero because multiplying one matrix costs nothing.

Use the chain length L from 2 to n.

Calculate cost q for each split and update minimum.

4

Print the minimum multiplication cost

Print the minimum multiplication cost stored in m[0][n-1] using printf with the format string "Minimum number of multiplications is %d\n".

DSA C

int dims[] = {40, 20, 30, 10, 30};
int n = sizeof(dims) / sizeof(dims[0]) - 1;
int m[n][n];

for (int i = 0; i < n; i++) {
    m[i][i] = 0;
}

for (int L = 2; L <= n; L++) {
    for (int i = 0; i <= n - L; i++) {
        int j = i + L - 1;
        m[i][j] = 2147483647; // large number for infinity
        for (int k = i; k < j; k++) {
            int q = m[i][k] + m[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
            if (q < m[i][j]) {
                m[i][j] = q;
            }
        }
    }
}
// Your code here

Hint

Print the value m[0][n-1] which holds the minimum multiplication cost for the full chain.