Matrix Chain Multiplication in DSA C - Execution Trace

Concept Flow - Matrix Chain Multiplication

Start with matrix dimensions array p

↓

Initialize DP table m with zeros

↓

Set chain length l = 2 to n

↓

For each chain length l

↓

For i=1 to n-l+1

↓

Set m[i

↓

For k = i to j-1

↓

Calculate cost = m[i

↓

If cost < m[i

↓

Repeat for all k

↓

Repeat for all i

↓

Repeat for all l

↓

Result is m[1

The flow shows how the DP table is filled by increasing chain lengths, calculating minimal multiplication costs for matrix chains.

Execution Sample

DSA C

int matrixChainOrder(int p[], int n) {
  int m[n][n];
  for (int i = 1; i < n; i++) m[i][i] = 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 - 1; k++) {
        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;
      }
    }
  }
  return m[1][n-1];
}

This code calculates the minimum number of scalar multiplications needed to multiply a chain of matrices.

Execution Table

Step	Operation	Indices (i,j,k)	Cost Computed	DP Table Update	DP Table State (partial)
1	Initialize diagonal	i=1..4, j=i	0	m[i][i] = 0	[[0, -, -, -, -], [-, 0, -, -, -], [-, -, 0, -, -], [-, -, -, 0, -], [-, -, -, -, 0]]
2	Chain length l=2	i=1, j=2, k=1	p[0]*p[1]*p[2] = 10*20*30=6000	m[1][2] = 6000	[[0, 6000, -, -, -], [-, 0, -, -, -], [-, -, 0, -, -], [-, -, -, 0, -], [-, -, -, -, 0]]
3	Chain length l=2	i=2, j=3, k=2	p[1]*p[2]*p[3] = 20*30*40=24000	m[2][3] = 24000	[[0, 6000, -, -, -], [-, 0, 24000, -, -], [-, -, 0, -, -], [-, -, -, 0, -], [-, -, -, -, 0]]
4	Chain length l=2	i=3, j=4, k=3	p[2]*p[3]*p[4] = 30*40*30=36000	m[3][4] = 36000	[[0, 6000, -, -, -], [-, 0, 24000, -, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
5	Chain length l=3	i=1, j=3, k=1	m[1][1]+m[2][3]+p[0]*p[1]*p[3] = 0+24000+10*20*40=32000	m[1][3] = 32000	[[0, 6000, 32000, -, -], [-, 0, 24000, -, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
6	Chain length l=3	i=1, j=3, k=2	m[1][2]+m[3][3]+p[0]*p[2]*p[3] = 6000+0+10*30*40=18000	m[1][3] = 18000 (updated)	[[0, 6000, 18000, -, -], [-, 0, 24000, -, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
7	Chain length l=3	i=2, j=4, k=2	m[2][2]+m[3][4]+p[1]*p[2]*p[4] = 0+36000+20*30*30=54000	m[2][4] = 54000	[[0, 6000, 18000, -, -], [-, 0, 24000, 54000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
8	Chain length l=3	i=2, j=4, k=3	m[2][3]+m[4][4]+p[1]*p[3]*p[4] = 24000+0+20*40*30=48000	m[2][4] = 48000 (updated)	[[0, 6000, 18000, -, -], [-, 0, 24000, 48000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
9	Chain length l=4	i=1, j=4, k=1	m[1][1]+m[2][4]+p[0]*p[1]*p[4] = 0+48000+10*20*30=54000	m[1][4] = 54000	[[0, 6000, 18000, 54000, -], [-, 0, 24000, 48000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
10	Chain length l=4	i=1, j=4, k=2	m[1][2]+m[3][4]+p[0]*p[2]*p[4] = 6000+36000+10*30*30=66000	m[1][4] = 54000 (unchanged)	[[0, 6000, 18000, 54000, -], [-, 0, 24000, 48000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
11	Chain length l=4	i=1, j=4, k=3	m[1][3]+m[4][4]+p[0]*p[3]*p[4] = 18000+0+10*40*30=30000	m[1][4] = 30000 (updated)	[[0, 6000, 18000, 30000, -], [-, 0, 24000, 48000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
12	End	-	-	-	Minimum cost is m[1][4] = 30000

💡 All chain lengths processed; minimal multiplication cost found at m[1][n-1]

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 11	Final
m[1][1]	-	0	0	0	0
m[1][2]	-	-	6000	6000	6000
m[1][3]	-	-	32000	18000	18000
m[1][4]	-	-	-	-	30000
m[2][3]	-	0	24000	24000	24000
m[2][4]	-	-	54000	48000	48000
m[3][4]	-	0	36000	36000	36000

Key Moments - 3 Insights

Why do we start filling the DP table from chain length 2, not 1?

Because multiplying a single matrix (chain length 1) requires zero multiplications, so m[i][i] is set to 0 initially (see Step 1). The actual multiplication cost calculation starts from chain length 2 (Step 2).

Why do we check all k between i and j-1 when computing m[i][j]?

Each k represents a possible place to split the matrix chain. We try all splits to find the minimal cost (see Steps 5-11). This ensures we find the best order to multiply matrices.

Why does m[i][j] get updated multiple times for the same i,j?

Because for each k, we compute a cost and update m[i][j] if the cost is smaller (see Steps 6 and 8). This finds the minimal multiplication cost among all splits.

Visual Quiz - 3 Questions

Look at the execution table at Step 6. What is the updated value of m[1][3]?

A 32000

B 6000

C 18000

D 24000

💡 Hint

Check the 'DP Table Update' and 'DP Table State' columns at Step 6 in the execution table.

At which step does the minimal cost for multiplying matrices 1 to 4 get finalized?

A Step 10

B Step 11

C Step 9

D Step 12

💡 Hint

Look at the 'DP Table Update' column for m[1][4] updates in Steps 9 to 11.

If the dimension p[2] changed from 30 to 25, which step's cost calculation would be directly affected?

A Step 11

B Step 4

C Step 2

D Step 6

💡 Hint

Check the cost formulas in the execution table rows and see where p[2] is multiplied.

Concept Snapshot

Matrix Chain Multiplication:
- Input: array p of matrix dimensions (length n)
- DP table m[i][j] stores min multiplications for matrices i..j
- Initialize m[i][i] = 0
- Fill m by increasing chain length l from 2 to n-1
- For each (i,j), try all splits k to minimize cost
- Result: m[1][n-1] is minimal multiplication cost

Full Transcript

Matrix Chain Multiplication finds the least number of scalar multiplications needed to multiply a chain of matrices. We use a DP table m where m[i][j] holds the minimal cost for multiplying matrices from i to j. We start by setting m[i][i] = 0 because a single matrix needs no multiplication. Then, for chain lengths from 2 to n-1, we compute m[i][j] by trying all possible splits k between i and j-1. For each split, we calculate the cost as the sum of costs of multiplying the two subchains plus the cost of multiplying the resulting matrices. We update m[i][j] with the minimal cost found. After filling the table, m[1][n-1] gives the minimal multiplication cost for the entire chain. The execution table shows step-by-step how the DP table is filled and updated, tracking costs and decisions. Key moments clarify why we start from chain length 2, why all splits are checked, and why multiple updates happen for the same cell. The visual quiz tests understanding of table updates and cost calculations. This method efficiently solves the problem by avoiding repeated calculations.

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