Matrix Chain Multiplication in DSA Typescript - Execution Trace

Concept Flow - Matrix Chain Multiplication

Start with matrices dimensions

↓

Initialize DP table with zeros on diagonal

↓

For chain length = 2 to n

↓

For each start index i

↓

For each split point k between i and j

↓

Calculate cost = cost_left + cost_right + multiplication cost

↓

Update DP[i

↓

Repeat until full chain cost computed

↓

Result in DP[0

The flow shows how we fill a table step-by-step to find the cheapest way to multiply a chain of matrices.

Execution Sample

DSA Typescript

const dims = [10, 20, 30, 40];
const n = dims.length - 1;
const dp = Array(n).fill(0).map(() => Array(n).fill(0));
for (let length = 2; length <= n; length++) {
  for (let i = 0; i <= n - length; i++) {
    let j = i + length - 1;
    dp[i][j] = Infinity;
    for (let k = i; k < j; k++) {
      const cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}

This code calculates the minimum multiplication cost for matrices with given dimensions.

Execution Table

Step	Operation	Indices (i,j)	Split k	Cost Calculated	DP Table State	Minimum Cost at DP[i][j]
1	Initialize diagonal	0,0	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
2	Initialize diagonal	1,1	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
3	Initialize diagonal	2,2	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
4	Calculate cost for length=2	0,1	0	10*20*30=6000	[[0, 6000, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	6000
5	Calculate cost for length=2	1,2	1	20*30*40=24000	[[0, 6000, -, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	24000
6	Calculate cost for length=3	0,2	0	dp[0][0]+dp[1][2]+10*20*40=0+24000+8000=32000	[[0, 6000, 32000, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	32000
7	Calculate cost for length=3	0,2	1	dp[0][1]+dp[2][2]+10*30*40=6000+0+12000=18000	[[0, 6000, 18000, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	18000
8	Calculate cost for length=4	0,3	0	dp[0][0]+dp[1][3]+10*20*40=0+Infinity+8000=Infinity	[[0, 6000, 18000, Infinity], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	Infinity
9	Calculate cost for length=4	0,3	1	dp[0][1]+dp[2][3]+6000+12000=6000+Infinity+12000=Infinity	[[0, 6000, 18000, Infinity], [-, 0, 24000, Infinity], [-, -, 0, -], [-, -, -, 0]]	Infinity
10	Calculate cost for length=4	0,3	2	dp[0][2]+dp[3][3]+18000+48000=18000+0+48000=66000	[[0, 6000, 18000, 66000], [-, 0, 24000, Infinity], [-, -, 0, -], [-, -, -, 0]]	66000
11	Calculate cost for length=4	1,3	1	dp[1][1]+dp[2][3]+0+12000=0+Infinity+12000=Infinity	[[0, 6000, 18000, 66000], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	Infinity
12	Calculate cost for length=4	1,3	2	dp[1][2]+dp[3][3]+24000+48000=24000+0+48000=72000	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, -], [-, -, -, 0]]	72000
13	Calculate cost for length=4	2,3	2	dp[2][2]+dp[3][3]+30*40*?=0+0+?	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, 1200], [-, -, -, 0]]	1200
14	Final result	0,3	-	-	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, 1200], [-, -, -, 0]]	66000

💡 All subproblems computed; minimum multiplication cost is dp[0][n-1] = 66000

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 10	After Step 12	Final
dp[0][0]	0	0	0	0	0	0	0
dp[1][1]	0	0	0	0	0	0	0
dp[2][2]	0	0	0	0	0	0	0
dp[3][3]	0	0	0	0	0	0	0
dp[0][1]	Infinity	6000	6000	6000	6000	6000	6000
dp[1][2]	Infinity	Infinity	24000	24000	24000	24000	24000
dp[0][2]	Infinity	Infinity	Infinity	18000	18000	18000	18000
dp[0][3]	Infinity	Infinity	Infinity	Infinity	66000	66000	66000
dp[1][3]	Infinity	Infinity	Infinity	Infinity	Infinity	72000	72000
dp[2][3]	Infinity	Infinity	Infinity	Infinity	Infinity	Infinity	1200

Key Moments - 3 Insights

Why do we initialize the diagonal of the DP table with zeros?

Because multiplying one matrix alone costs nothing, so dp[i][i] = 0 as shown in steps 1-3 of the execution_table.

Why do we try all split points k between i and j?

Because the chain can be split in different ways, and we want the minimum cost. The execution_table rows 6-7 show different k values and costs compared.

Why does the cost formula include dims[i]*dims[k+1]*dims[j+1]?

This represents the cost of multiplying two matrices after splitting at k. It matches the multiplication dimension rule and is used in cost calculations in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What is the minimum cost stored at dp[0][2] after considering split k=1?

A 32000

B 18000

C 6000

D 24000

💡 Hint

Check the 'Minimum Cost at DP[i][j]' column in row 7 of the execution_table.

At which step does the DP table first get a value for dp[0][1]?

A Step 4

B Step 6

C Step 2

D Step 10

💡 Hint

Look for when dp[0][1] changes from '-' or Infinity to a number in the execution_table.

If the dimension array dims changed to [10, 20, 10, 40], how would the cost at step 7 change?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Look at the cost formula in step 7 and consider how dims[k+1] affects multiplication cost.

Concept Snapshot

Matrix Chain Multiplication:
- Goal: Minimize scalar multiplications for matrix chain
- Use DP table dp[i][j] for min cost multiplying matrices i to j
- dp[i][i] = 0 (single matrix)
- For length 2 to n, compute dp[i][j] by trying all splits k
- Cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
- Result in dp[0][n-1]

Full Transcript

Matrix Chain Multiplication finds the cheapest way to multiply a sequence of matrices. We use a table dp where dp[i][j] stores the minimum cost to multiply matrices from i to j. The diagonal dp[i][i] is zero because one matrix alone needs no multiplication. We fill the table by increasing chain length, trying all split points k between i and j. For each split, we calculate cost as sum of left and right parts plus multiplication cost of resulting matrices. We keep the minimum cost in dp[i][j]. After filling the table, dp[0][n-1] gives the minimum multiplication cost for the full chain. The execution table shows step-by-step how costs are computed and updated. Key points include initializing the diagonal, trying all splits, and using the dimension array to calculate multiplication cost.