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.

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

A. To find the minimum number of scalar multiplications needed to multiply a chain of matrices

B. To multiply all matrices in the chain directly without optimization

C. To find the maximum number of matrices that can be multiplied

D. To count the total number of matrices in the chain

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices so that the total number of scalar multiplications is minimized.

2. Step 2: Identify the correct goal

   Among the options, only To find the minimum number of scalar multiplications needed to multiply a chain of matrices describes minimizing scalar multiplications, which is the main goal.

3. Final Answer:

   To find the minimum number of scalar multiplications needed to multiply a chain of matrices -> Option A

4. Quick Check:

   Goal = minimize multiplications [OK]

Hint: Remember: minimize multiplication cost, not count matrices [OK]

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing counting matrices with minimizing operations
• Assuming maximum matrices multiplication is the goal

2. Which of the following is the correct way to declare the dimensions array p for 4 matrices with dimensions 10x20, 20x30, 30x40, and 40x50 in C?

easy

A. int p[5] = {10, 20, 30, 40};

B. int p[4] = {10, 20, 30, 40};

C. int p[4] = {10, 20, 30, 40, 50};

D. int p[5] = {10, 20, 30, 40, 50};

Solution

1. Step 1: Understand the dimensions array size

   For n matrices, the dimensions array size is n+1. Here, 4 matrices need an array of size 5.

2. Step 2: Check the array values

   The array should list the row count of the first matrix and then the column counts of each matrix in order: {10, 20, 30, 40, 50}.

3. Final Answer:

   int p[5] = {10, 20, 30, 40, 50}; -> Option D

4. Quick Check:

   Array size = matrices + 1, values match dimensions [OK]

Hint: Dimensions array length = number of matrices + 1 [OK]

Common Mistakes:

• Using array size equal to number of matrices instead of number + 1
• Missing the last dimension in the array
• Including extra or fewer elements than needed

3. What is the output of the following C code snippet for Matrix Chain Multiplication cost calculation?

int p[] = {5, 10, 3, 12, 5};
int n = 4;
int m[5][5] = {0};

for (int L = 2; L <= n; L++) {
    for (int i = 1; i <= n - L + 1; i++) {
        int j = i + L - 1;
        m[i][j] = 1000000;
        for (int 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;
        }
    }
}
printf("%d", m[1][n]);

medium

A. 201

B. 405

C. 270

D. 150

Solution

1. Step 1: Understand the matrix dimensions and initialization

   p = {5,10,3,12,5} means matrices: 5x10, 10x3, 3x12, 12x5. The code calculates minimum multiplication cost using dynamic programming.

2. Step 2: Calculate minimum cost m[1][4]

   Calculations:
   - m[1][2] = 5*10*3 = 150
   - m[2][3] = 10*3*12 = 360
   - m[3][4] = 3*12*5 = 180
   Then:
   - m[1][3] = min( m[1][1]+m[2][3]+5*10*12=0+360+600=960, m[1][2]+m[3][3]+5*3*12=150+0+180=330 ) = 330
   - m[2][4] = min( m[2][2]+m[3][4]+10*3*5=0+180+150=330, m[2][3]+m[4][4]+10*12*5=360+0+600=960 ) = 330
   Finally:
   - m[1][4] = min( m[1][1]+m[2][4]+5*10*5=0+330+250=580, m[1][2]+m[3][4]+5*3*5=150+180+75=405, m[1][3]+m[4][4]+5*12*5=330+0+300=630 ) = 405

3. Final Answer:

   405 -> Option B

4. Quick Check:

   Minimum cost = 405 [OK]

Hint: Trace inner loops carefully to find minimum cost [OK]

Common Mistakes:

• Misindexing arrays starting from 0 instead of 1
• Incorrectly calculating multiplication costs
• Ignoring initialization of m[i][j]

4. Identify the error in the following C code snippet for Matrix Chain Multiplication and select the fix:

int p[] = {2, 3, 4};
int n = 2;
int m[3][3] = {0};
for (int L = 2; L <= n; L++) {
    for (int i = 1; i <= n - L + 1; i++) {
        int j = i + L - 1;
        m[i][j] = INT_MAX;
        for (int k = i; k < j; k++) {
            int q = m[i][k] + m[k+1][j] + p[i]*p[k]*p[j];
            if (q < m[i][j])
                m[i][j] = q;
        }
    }
}
printf("%d", m[1][n]);

medium

A. Change p[i]*p[k]*p[j] to p[i-1]*p[k]*p[j]

B. Initialize m array with -1 instead of 0

C. Change loop to start i from 0 instead of 1

D. Use float instead of int for m array

Solution

1. Step 1: Identify the indexing error in cost calculation

   The multiplication cost formula uses p[i]*p[k]*p[j], but correct indexing for dimensions array is p[i-1]*p[k]*p[j] because p has length n+1 and matrices are from i to j.

2. Step 2: Fix the formula to use correct indices

   Changing to p[i-1]*p[k]*p[j] fixes the dimension mismatch and ensures correct cost calculation.

3. Final Answer:

   Change p[i]*p[k]*p[j] to p[i-1]*p[k]*p[j] -> Option A

4. Quick Check:

   Dimension indexing = p[i-1]*p[k]*p[j] [OK]

Hint: Remember dimension array indexing starts at i-1 for cost [OK]

Common Mistakes:

• Using wrong indices in multiplication cost formula
• Not initializing m array properly
• Incorrect loop ranges causing out-of-bound errors

5. Given matrices with dimensions p = {40, 20, 30, 10, 30}, what is the minimum number of scalar multiplications needed to multiply the chain? Use the Matrix Chain Multiplication approach.

hard

A. 18000

B. 30000

C. 26000

D. 24000

Solution

1. Step 1: Understand matrix dimensions and problem size

   p = {40, 20, 30, 10, 30} means matrices: 40x20, 20x30, 30x10, 10x30. We need minimum multiplication cost for 4 matrices.

2. Step 2: Calculate minimum multiplication cost using DP

   Calculate costs:
   - m[1][2] = 40*20*30 = 24000
   - m[2][3] = 20*30*10 = 6000
   - m[3][4] = 30*10*30 = 9000
   Calculate m[1][3]:
   - (m[1][1]+m[2][3]+40*20*10) = 0 + 6000 + 8000 = 14000
   - (m[1][2]+m[3][3]+40*30*10) = 24000 + 0 + 12000 = 36000
   Minimum = 14000
   Calculate m[2][4]:
   - (m[2][2]+m[3][4]+20*30*30) = 0 + 9000 + 18000 = 27000
   - (m[2][3]+m[4][4]+20*10*30) = 6000 + 0 + 6000 = 12000
   Minimum = 12000
   Calculate m[1][4]:
   - (m[1][1]+m[2][4]+40*20*30) = 0 + 12000 + 24000 = 36000
   - (m[1][2]+m[3][4]+40*30*30) = 24000 + 9000 + 36000 = 69000
   - (m[1][3]+m[4][4]+40*10*30) = 14000 + 0 + 12000 = 26000
   Minimum = 26000

3. Final Answer:

   26000 -> Option C

4. Quick Check:

   Minimum scalar multiplications = 26000 [OK]

Hint: Calculate costs for all splits, pick minimum [OK]

Common Mistakes:

• Calculating only one split instead of all
• Mixing up matrix dimensions in multiplication
• Forgetting to add multiplication costs properly