Matrix Chain Multiplication in DSA C++ - Execution Trace

Concept Flow - Matrix Chain Multiplication

Start with matrix dimensions array p

↓

Initialize DP table m and s

↓

For chain length l = 2 to n-1

↓

For i = 1 to n-l

↓

j = i + l - 1

↓

Set m[i

↓

For k = i to j-1

↓

Calculate cost = m[i

↓

If cost < m[i

↓

Repeat until all subproblems solved

↓

Result: m[1

↓

Use s table to print optimal parenthesization

This flow shows how we fill a table to find the cheapest way to multiply a chain of matrices by trying all split points.

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; 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 with given dimensions.

Execution Table

Step	Operation	Indices (i,j,k)	Cost Computed	m[i][j] Updated	Current m Table State
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	[[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	[[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=51000	m[1][4] = 51000	[[0, 6000, 18000, 51000, -], [-, 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	[[0, 6000, 18000, 30000, -], [-, 0, 24000, 48000, -], [-, -, 0, 36000, -], [-, -, -, 0, -], [-, -, -, -, 0]]
12	End	-	-	-	Minimum cost m[1][4] = 30000

💡 All subproblems computed; m[1][4] holds minimum multiplication cost

Variable Tracker

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

Key Moments - 3 Insights

Why do we initialize m[i][i] to 0?

Because multiplying one matrix alone requires no multiplication, so cost is zero. See execution_table row 1 where diagonal m[i][i] is set to 0.

Why do we try all k between i and j-1?

Because k represents where we split the chain into two parts. Trying all k finds the minimal cost. See execution_table rows 5-11 where different k values are tested.

Why does m[i][j] get updated only if cost < current m[i][j]?

Because we want the minimum multiplication cost. We keep the smallest cost found so far. See execution_table rows 6 and 11 where m[i][j] is updated only when cost is less.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of m[1][3] after updating?

A 32000

B 18000

C 24000

D 6000

💡 Hint

Check the 'm[i][j] Updated' and 'Current m Table State' columns at step 6.

At which step does m[1][4] first get its minimum value?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at the 'm[i][j] Updated' column for m[1][4] in steps 9 to 11.

If the dimension p[2] changed from 30 to 25, how would the cost at step 6 change?

A It would increase

B It would decrease

C It would stay the same

D Cannot determine

💡 Hint

Step 6 cost formula: m[1][2]+m[3][3]+p[0]*p[2]*p[3], changing p[2] affects multiplication cost.

Concept Snapshot

Matrix Chain Multiplication:
- Input: array p of matrix dimensions (length n)
- Goal: minimize scalar multiplications to multiply matrices A1..An
- Use DP table m[i][j] for min cost of multiplying Ai..Aj
- Try all splits k between i and j-1
- m[i][j] = min over k of (m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
- Result in m[1][n-1]

Full Transcript

Matrix Chain Multiplication finds the cheapest way to multiply a chain of matrices. We use a table m where m[i][j] stores the minimum cost to multiply matrices from i to j. We start by setting m[i][i] to zero because a single matrix needs no multiplication. Then, for increasing chain lengths, we try all possible split points k between i and j-1. For each k, we calculate the cost of multiplying the two parts plus the cost of multiplying the resulting matrices. We update m[i][j] if we find a cheaper cost. After filling the table, m[1][n-1] gives the minimum multiplication cost. This method avoids repeated calculations by storing results of subproblems.

Practice

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

easy

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

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

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

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 to minimize computation.

2. Step 2: Identify the correct goal

   The goal is to minimize the number of scalar multiplications, not just multiply or count matrices.

3. Final Answer:

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

4. Quick Check:

   Goal = Minimum multiplications [OK]

Hint: Remember: minimize multiplication cost, not just multiply [OK]

Common Mistakes:

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

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

easy

A. int dims[] = {10, 20, 30, 40, 50};

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

C. int dims[] = {10, 20, 30, 40, 50, 60};

D. int dims[] = {20, 30, 40, 50};

Solution

1. Step 1: Understand the dimensions array format

   For n matrices, the dimensions array has n+1 elements representing rows and columns of each matrix.

2. Step 2: Apply to given matrices

   For matrices 10x20, 20x30, 30x40, 40x50, dims = {10, 20, 30, 40, 50}.

3. Final Answer:

   int dims[] = {10, 20, 30, 40, 50}; -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Using fewer elements than needed in the dimensions array
• Including extra unrelated numbers
• Confusing matrix dimensions order

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

int dims[] = {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 cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j]) m[i][j] = cost;
    }
  }
}
std::cout << m[1][n] << std::endl;

medium

A. 270

B. 150

C. 201

D. 405

Solution

1. Step 1: Understand matrix dimensions and indices

   Dimensions: 5x10, 10x3, 3x12, 12x5; n=4 matrices; m[i][j] stores min cost from i to j.

2. Step 2: Calculate minimum multiplication cost

   Length 2: m[1][2]=150, m[2][3]=360, m[3][4]=180
   Length 3: m[1][3]=min(0+360+600,150+0+180)=330; m[2][4]=min(0+180+150,360+0+600)=330
   Length 4: m[1][4]=min(0+330+250,150+180+75,330+0+300)=405

3. Final Answer:

   405 -> Option D

4. Quick Check:

   Minimum cost = 405 [OK]

Hint: Trace splits and pick minimum cost [OK]

Common Mistakes:

• Mixing up indices i, j, k
• Incorrect cost formula application
• Forgetting to initialize m[i][j] to max

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

int dims[] = {40, 20, 30, 10, 30};
int n = 4;
int m[5][5];
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] = 0;
    for (int k = i; k < j; k++) {
      int cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j])
        m[i][j] = cost;
    }
  }
}

medium

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

B. Initialize m[i][j] to INT_MAX instead of 0 before inner loop

C. Start i loop from 0 instead of 1

D. Remove the if condition inside the inner loop

Solution

1. Step 1: Identify initialization mistake

   m[i][j] is set to 0 before checking for minimum cost, which causes incorrect comparisons.

2. Step 2: Correct initialization

   m[i][j] should be initialized to a very large number (INT_MAX) to find minimum cost correctly.

3. Final Answer:

   Initialize m[i][j] to INT_MAX instead of 0 before inner loop -> Option B

4. Quick Check:

   Use INT_MAX to find minimum cost [OK]

Hint: Initialize costs to max before minimizing [OK]

Common Mistakes:

• Setting m[i][j] to 0 instead of INT_MAX
• Incorrect dims indexing causing wrong cost
• Ignoring initialization leading to wrong min

5. Given matrices with dimensions 10x15, 15x20, 20x25, and 25x30, what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the Matrix Chain Multiplication approach.

hard

A. 15500

B. 15000

C. 13000

D. 11250

Solution

1. Step 1: List matrix dimensions and possible splits

   Matrices: A1(10x15), A2(15x20), A3(20x25), A4(25x30). dims=[10,15,20,25,30]. Calculate costs for chain length 2 to 4.

2. Step 2: Calculate minimum costs for each subchain

   Length 2: m[1][2]=10*15*20=3000; m[2][3]=15*20*25=7500; m[3][4]=20*25*30=15000
   Length 3: m[1][3]=min(0+7500+10*15*25=11250, 3000+0+10*20*25=8000)=8000;
   m[2][4]=min(0+15000+15*20*30=24000, 7500+0+15*25*30=18750)=18750
   Length 4: m[1][4]=min(0+18750+10*15*30=23250, 3000+15000+10*20*30=24000, 8000+0+10*25*30=15500)=15500

3. Final Answer:

   15500 -> Option A

4. Quick Check:

   Minimum scalar multiplications = 15500 [OK]

Hint: Calculate costs for smaller chains first, then combine [OK]

Common Mistakes:

• Incorrectly calculating subproblems costs
• Mixing up matrix dimensions in cost formula
• Not checking all split points k