Matrix Chain Multiplication in DSA C

Mental Model

We want to find the best way to multiply a chain of matrices so that the total number of multiplications is as small as possible.

Analogy: Imagine you have several long ropes to tie together. The order in which you tie them affects how much effort you spend. Matrix Chain Multiplication is like finding the order to tie ropes that uses the least effort.

Matrices: A1(10x30) -> A2(30x5) -> A3(5x60)
Goal: Find best way to multiply A1xA2xA3

Chain:
[10x30] -> [30x5] -> [5x60]

Possible orders:
(A1xA2)xA3 or A1x(A2xA3)

Dry Run Walkthrough

Input: matrices dimensions: [10, 30, 5, 60] (means matrices A1:10x30, A2:30x5, A3:5x60)

Goal: Find the minimum number of scalar multiplications needed to multiply A1xA2xA3

Step 1: Calculate cost of multiplying A1 and A2 first, then multiply result with A3

Cost for (A1xA2) = 10x30x5 = 1500 multiplications
Then multiply result (10x5) with A3 (5x60): 10x5x60 = 3000
Total cost = 1500 + 3000 = 4500

Why: We try one way of parenthesizing to find its cost

Step 2: Calculate cost of multiplying A2 and A3 first, then multiply A1 with result

Cost for (A2xA3) = 30x5x60 = 9000 multiplications
Then multiply A1 (10x30) with result (30x60): 10x30x60 = 18000
Total cost = 9000 + 18000 = 27000

Why: We try the other way of parenthesizing to compare costs

Step 3: Compare both costs and choose the minimum

Minimum cost = 4500 multiplications by doing (A1xA2)xA3

Why: We want the least multiplication cost to optimize performance

Result:

Minimum multiplication cost = 4500

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

// Function to find minimum multiplication cost
int matrixChainOrder(int p[], int n) {
    int m[n][n];

    // cost is zero when multiplying one matrix
    for (int i = 1; i < n; i++)
        m[i][i] = 0;

    // L is chain length
    for (int L = 2; L <= n - 1; L++) {
        for (int i = 1; i <= n - L; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                // cost = cost of left + cost of right + cost of multiplying two parts
                int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < m[i][j])
                    m[i][j] = cost; // update min cost
            }
        }
    }
    return m[1][n - 1];
}

int main() {
    int arr[] = {10, 30, 5, 60};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = matrixChainOrder(arr, size);
    printf("Minimum multiplication cost = %d\n", result);
    return 0;
}

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

initialize cost zero for single matrix multiplication

for (int L = 2; L <= n - 1; L++) {

iterate over chain lengths from 2 to n-1

for (int i = 1; i <= n - L; i++) {

set start index of chain segment

int j = i + L - 1;

set end index of chain segment

m[i][j] = INT_MAX;

initialize min cost for this segment

for (int k = i; k <= j - 1; k++) {

try all possible split points

int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];

calculate cost for current split

if (cost < m[i][j]) m[i][j] = cost;

update min cost if current split is cheaper

Output

Minimum multiplication cost = 4500

Complexity Analysis

Time: O(n^3) because we check all chain lengths, start points, and split points

Space: O(n^2) because we store minimum costs for all subchains in a 2D table

vs Alternative: Naive approach tries all parenthesizations recursively with exponential time; DP reduces it to polynomial time

Edge Cases

Only one matrix (e.g., dimensions [10, 20])

Cost is zero because no multiplication needed

DSA C

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

Two matrices (e.g., dimensions [10, 20, 30])

Cost is direct multiplication cost of two matrices

DSA C

int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];

When to Use This Pattern

When you see a problem asking for the best order to perform multiple operations to minimize cost, use Matrix Chain Multiplication dynamic programming pattern.

Common Mistakes

Mistake: Starting indices from 0 instead of 1 for DP table causing wrong indexing
Fix: Use 1-based indexing for DP table to match matrix dimensions array indexing

Mistake: Not initializing diagonal of DP table to zero, leading to incorrect base cases
Fix: Set m[i][i] = 0 for all i to represent zero cost for single matrix

Summary

Finds the minimum number of scalar multiplications needed to multiply a chain of matrices.

Use when you want to optimize the order of matrix multiplications to reduce computation.

The key insight is to break the problem into smaller subproblems and combine their solutions using dynamic programming.