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.