Program Overview

This program calculates the optimal way to multiply a chain of matrices using dynamic programming. The goal is to minimize the number of scalar multiplications required to multiply the matrices together.

Program Structure

• Input: An array of matrix dimensions where each matrix is defined by its number of rows and columns.
• Dynamic Programming Table: A 2D array to store the minimum number of multiplications needed for matrix chain products.
• Output: The minimum number of scalar multiplications needed to multiply the entire chain of matrices.

C Program

#include 
#include 

// Function to calculate the minimum number of multiplications
int matrixChainMultiplication(int p[], int n) {
    int m[n][n]; // Table to store the minimum number of multiplications
    int i, j, k, l;

    // Initialize the table with 0 for single matrix multiplication
    for (i = 1; i < n; i++) {
        m[i][i] = 0;
    }

    // l is the 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; // Set initial value to a large number
            // Try every possible split
            for (k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q; // Update minimum if found a smaller one
                }
            }
        }
    }

    return m[1][n - 1]; // Return the minimum number of multiplications needed
}

// Main function
int main() {
    int n;
    printf("Enter the number of matrices: ");
    scanf("%d", &n);

    int p[n + 1]; // Array to store dimensions
    printf("Enter the dimensions of the matrices (rows and columns):\n");
    for (int i = 0; i < n + 1; i++) {
        scanf("%d", &p[i]);
    }

    // Calculate the minimum number of multiplications
    int minMultiplications = matrixChainMultiplication(p, n + 1);
    printf("The minimum number of multiplications needed: %d\n", minMultiplications);

    return 0;
}

Explanation of the Code

The program begins by defining the necessary functions and variables:

• The matrixChainMultiplication function implements dynamic programming to find the minimum multiplication cost:
  • A 2D array m is initialized to store the minimum number of multiplications for different matrix chains.
  • It iterates through different chain lengths and calculates the cost for multiplying matrices using nested loops.
  • For each possible split of the matrix chain, it calculates the total cost and updates the minimum if a smaller cost is found.
• The main function handles input and invokes the calculation function:
  • The user is prompted to enter the number of matrices and their dimensions.
  • It then calls the matrixChainMultiplication function and prints the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the number of matrices.
3. Input the dimensions of the matrices (rows and columns) in order.
4. The program will output the minimum number of multiplications required to multiply the chain of matrices.