Matrix Chain Multiplication in DSA Java - 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

↓

For i = 1 to n-l+1

↓

j = i + l - 1

↓

Try all splits k from i to j-1

↓

Calculate cost = m[i

↓

Update m[i

↓

Store k in s[i

↓

Repeat until full chain computed

↓

Result: m[1

↓

Use s to print optimal parenthesization

The flow shows how the DP table is filled by increasing chain lengths, trying all splits, and storing minimum costs and split points.

Execution Sample

DSA Java

int matrixChainOrder(int[] p) {
  int n = p.length - 1;
  int[][] m = new int[n+1][n+1];
  int[][] s = new int[n+1][n+1];
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i <= n-l+1; i++) {
      int j = i + l - 1;
      m[i][j] = Integer.MAX_VALUE;
      for (int k = i; k < j; 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;
          s[i][j] = k;
        }
      }
    }
  }
  return m[1][n];
}

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

Execution Table

Step	Chain Length (l)	i	j	k (Split)	Cost Calculation	Minimum Cost m[i][j]	Split Point s[i][j]	DP Table m State (partial)
1	2	1	2	1	m[1][1] + m[2][2] + p[0]*p[1]*p[2] = 0 + 0 + 10*20*30 = 6000	6000	1	m[1][2]=6000
2	2	2	3	2	m[2][2] + m[3][3] + p[1]*p[2]*p[3] = 0 + 0 + 20*30*40 = 24000	24000	2	m[1][2]=6000, m[2][3]=24000
3	2	3	4	3	m[3][3] + m[4][4] + p[2]*p[3]*p[4] = 0 + 0 + 30*40*30 = 36000	36000	3	m[1][2]=6000, m[2][3]=24000, m[3][4]=36000
4	3	1	3	1	m[1][1] + m[2][3] + p[0]*p[1]*p[3] = 0 + 24000 + 10*20*40 = 32000	32000	1	m[1][3]=32000 (temp)
5	3	1	3	2	m[1][2] + m[3][3] + p[0]*p[2]*p[3] = 6000 + 0 + 10*30*40 = 18000	18000	2	m[1][3]=18000 (updated)
6	3	2	4	2	m[2][2] + m[3][4] + p[1]*p[2]*p[4] = 0 + 36000 + 20*30*30 = 54000	54000	2	m[2][4]=54000 (temp)
7	3	2	4	3	m[2][3] + m[4][4] + p[1]*p[3]*p[4] = 24000 + 0 + 20*40*30 = 48000	48000	3	m[2][4]=48000 (updated)
8	4	1	4	1	m[1][1] + m[2][4] + p[0]*p[1]*p[4] = 0 + 48000 + 10*20*30 = 54000	54000	1	m[1][4]=54000 (temp)
9	4	1	4	2	m[1][2] + m[3][4] + p[0]*p[2]*p[4] = 6000 + 36000 + 10*30*30 = 51000	51000	2	m[1][4]=51000 (updated)
10	4	1	4	3	m[1][3] + m[4][4] + p[0]*p[3]*p[4] = 18000 + 0 + 10*40*30 = 30000	30000	3	m[1][4]=30000 (final)
Exit	-	-	-	-	-	-	-	All subproblems computed, minimum cost m[1][4] = 30000

💡 All subproblems computed, minimum cost m[1][n] found, algorithm ends

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 7	After Step 10
m[1][2]	0	6000	6000	6000	6000	6000	6000
m[2][3]	0	0	24000	24000	24000	24000	24000
m[1][3]	0	0	0	0	18000	18000	18000
m[3][4]	0	0	0	36000	36000	36000	36000
m[2][4]	0	0	0	0	0	48000	48000
m[1][4]	0	0	0	0	0	0	30000
s[1][2]	0	1	1	1	1	1	1
s[2][3]	0	0	2	2	2	2	2
s[1][3]	0	0	0	0	2	2	2
s[3][4]	0	0	0	3	3	3	3
s[2][4]	0	0	0	0	0	3	3
s[1][4]	0	0	0	0	0	0	3

Key Moments - 3 Insights

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

Because the optimal way to multiply matrices from i to j depends on where we split the chain. Trying all k ensures we find the minimum cost. See execution_table rows 4 and 5 where different k values give different costs.

Why is m[i][i] always zero?

Because multiplying one matrix alone requires no multiplication operations. This is the base case, shown as zero cost in the variable_tracker for m[i][i].

How does the DP table m get updated with minimum costs?

For each subchain, we calculate cost for all splits k and update m[i][j] only if the new cost is less. This is shown in execution_table rows 4 and 5 where m[1][3] is updated from 32000 to 18000.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the minimum cost m[1][3]?

A 32000

B 18000

C 6000

D 24000

💡 Hint

Check the 'Minimum Cost m[i][j]' column at step 5 in execution_table

At which step does m[3][4] get its value assigned?

A Step 3

B Step 2

C Step 14

D Step 1

💡 Hint

Look for m[3][4] in the 'DP Table m State (partial)' column in execution_table

If the dimension p[2] changed from 30 to 50, which part of the execution_table would change?

A Cost calculations involving p[2], like steps 3, 4, 6, 7

B Only the base cases where cost is zero

C No changes, since p[2] is not used

D Only the final result m[1][n]

💡 Hint

Check 'Cost Calculation' column for terms involving p[2] in execution_table

Concept Snapshot

Matrix Chain Multiplication:
- Input: array p of matrix dimensions
- Use DP table m[i][j] for min cost of multiplying Ai..Aj
- Try all splits k between i and j-1
- Cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
- Store min cost in m[i][j] and split point in s[i][j]
- Result: m[1][n] is minimum multiplications needed

Full Transcript

Matrix Chain Multiplication finds the minimum number of scalar multiplications needed to multiply a chain of matrices. We use a dynamic programming table m where m[i][j] stores the minimum cost to multiply matrices from i to j. We fill this table by increasing chain length l from 2 to n. For each subchain, we try all possible splits k and calculate the cost of multiplying the two parts plus the cost of multiplying the resulting matrices. We update m[i][j] with the minimum cost found and store the split point in s[i][j]. The base case is when i equals j, meaning one matrix, so cost is zero. After filling the table, m[1][n] gives the minimum multiplication cost. The execution table shows step-by-step how costs are calculated and updated. The variable tracker shows how m and s tables evolve. Key moments clarify why all splits are tried, why base costs are zero, and how updates happen. The visual quiz tests understanding of these steps.

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

2. Step 2: Identify the cost metric

   The cost is measured by the number of scalar multiplications needed, not just multiplying matrices directly.

3. Final Answer:

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

4. Quick Check:

   Goal = minimum scalar multiplications [OK]

Hint: Focus on minimizing multiplication cost, not counting matrices [OK]

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing number of matrices with multiplication cost
• Assuming maximum matrices multiplied 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 Java?

easy

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

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

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

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

Solution

1. Step 1: Understand the dimensions array format

   For n matrices, the dimensions array has length n+1, storing rows of first matrix and columns of each matrix.

2. Step 2: Apply to given matrices

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

3. Final Answer:

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

4. Quick Check:

   Length = 5 for 4 matrices [OK]

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

Common Mistakes:

• Using length equal to number of matrices instead of number+1
• Repeating dimensions unnecessarily
• Including extra unrelated dimensions

3. What will be the output of the following Java code snippet for matrix chain multiplication cost calculation?

int[] dims = {5, 10, 3};
int n = dims.length;
int[][] dp = new int[n][n];
for (int l = 2; l < n; l++) {
  for (int i = 1; i < n - l + 1; i++) {
    int j = i + l - 1;
    dp[i][j] = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
      int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}
System.out.println(dp[1][n-1]);

medium

A. 0

B. 75

C. 150

D. Syntax Error

Solution

1. Step 1: Understand the input matrices

   Dimensions: 5x10 and 10x3 matrices. Only one way to multiply.

2. Step 2: Calculate multiplication cost

   Cost = 5*10*3 = 150 scalar multiplications.

3. Final Answer:

   150 -> Option C

4. Quick Check:

   5*10*3 = 150 [OK]

Hint: Multiply dims[i-1]*dims[k]*dims[j] for cost [OK]

Common Mistakes:

• Confusing indices in cost calculation
• Assuming zero cost for single multiplication
• Syntax errors from incorrect loops

4. Identify the error in the following Java code snippet for matrix chain multiplication:

int[] dims = {2, 3, 4};
int n = dims.length;
int[][] dp = new int[n][n];
for (int l = 2; l <= n; l++) {
  for (int i = 1; i <= n - l + 1; i++) {
    int j = i + l - 1;
    dp[i][j] = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
      int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}
System.out.println(dp[1][n-1]);

medium

A. Loop condition l <= n causes ArrayIndexOutOfBoundsException

B. Incorrect cost calculation formula

C. dp array should be one-dimensional

D. Missing initialization of dp array

Solution

1. Step 1: Analyze loop bounds

   Outer loop runs l from 2 to n inclusive, but dp indices go up to n-1.

2. Step 2: Identify index error

   When l = n, j = i + l - 1 can exceed dp array size causing ArrayIndexOutOfBoundsException.

3. Final Answer:

   Loop condition l <= n causes ArrayIndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop bound off by one causes index error [OK]

Hint: Check loop bounds carefully to avoid index errors [OK]

Common Mistakes:

• Using <= n instead of < n for loop limit
• Ignoring array size limits
• Misunderstanding dp array dimensions

5. Given matrices with dimensions {40, 20, 30, 10, 30}, what is the minimum number of scalar multiplications needed to multiply the entire chain?

hard

A. 30000

B. 26000

C. 18000

D. 35000

Solution

1. Step 1: Understand matrix dimensions

   Matrices: 40x20, 20x30, 30x10, 10x30.

2. Step 2: Calculate minimum cost using dynamic programming

   Possible parenthesizations and costs:
   - ((40x20)x30)x(10x30):
   Cost1 = 40*20*30=24000 + 40*30*10=12000 + 0 = 36000 (too high)
   - (40x(20x30))x(10x30):
   Cost2 = 20*30*10=6000 + 40*20*10=8000 + 40*10*30=12000 = 26000 (minimum)

3. Final Answer:

   26000 -> Option B

4. Quick Check:

   Minimum scalar multiplications = 26000 [OK]

Hint: Try all splits and pick minimum cost [OK]

Common Mistakes:

• Calculating cost for only one parenthesization
• Mixing up matrix dimensions order
• Ignoring intermediate multiplication costs