Matrix Chain Multiplication in DSA Python - Execution Trace

Concept Flow - Matrix Chain Multiplication

Start with matrices dimensions

↓

Initialize DP table for costs

↓

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 table with minimum cost

↓

Repeat until full chain cost computed

↓

Return minimum multiplication cost for full chain

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 Python

dims = [10, 20, 30]
# matrices: A(10x20), B(20x30)

m = [[0, 0],
     [0, 0]]

# compute cost for chain length 2
m[0][1] = dims[0]*dims[1]*dims[2]
print(m[0][1])

This code calculates the cost of multiplying two matrices A and B with given dimensions.

Execution Table

Step	Operation	Chain Length	i	j	k	Cost Computed	DP Table State	Visual State
1	Initialize DP table with zeros	-	-	-	-	-	[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Empty DP table for 4 matrices
2	Set chain length = 2	2	-	-	-	-	[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Start filling for pairs
3	Calculate cost for i=0, j=1, k=0	2	0	1	0	10*20*30=6000	[[0, 6000, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Cost for multiplying A0 and A1
4	Calculate cost for i=1, j=2, k=1	2	1	2	1	20*30*40=24000	[[0, 6000, 0, 0], [0, 0, 24000, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Cost for multiplying A1 and A2
5	Set chain length = 3	3	-	-	-	-	[[0, 6000, 0, 0], [0, 0, 24000, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Start filling for triplets
6	Calculate cost for i=0, j=2, k=0	3	0	2	0	m[0][0]+m[1][2]+10*20*40=0+24000+8000=32000	[[0, 6000, 32000, 0], [0, 0, 24000, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Split at k=0
7	Calculate cost for i=0, j=2, k=1	3	0	2	1	m[0][1]+m[2][2]+10*30*40=6000+0+12000=18000	[[0, 6000, 18000, 0], [0, 0, 24000, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Split at k=1, choose min cost
8	Set chain length = 4	4	-	-	-	-	[[0, 6000, 18000, 0], [0, 0, 24000, 0], [0, 0, 0, 0], [0, 0, 0, 0]]	Start filling for quadruplets
9	Calculate cost for i=1, j=3, k=1	4	1	3	1	m[1][1]+m[2][3]+20*30*50=0+60000+30000=90000	[[0, 6000, 18000, 0], [0, 0, 24000, 90000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Split at k=1
10	Calculate cost for i=1, j=3, k=2	4	1	3	2	m[1][2]+m[3][3]+24000+0+20*40*50=24000+0+40000=64000	[[0, 6000, 18000, 0], [0, 0, 24000, 64000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Split at k=2, choose min cost
11	Calculate cost for i=0, j=3, k=0	4	0	3	0	m[0][0]+m[1][3]+0+64000+10*20*50=0+64000+10000=74000	[[0, 6000, 18000, 74000], [0, 0, 24000, 64000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Split at k=0
12	Calculate cost for i=0, j=3, k=1	4	0	3	1	m[0][1]+m[2][3]+6000+60000+10*30*50=66000+15000=81000	[[0, 6000, 18000, 74000], [0, 0, 24000, 64000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Split at k=1
13	Calculate cost for i=0, j=3, k=2	4	0	3	2	m[0][2]+m[3][3]+18000+0+10*40*50=18000+0+20000=38000	[[0, 6000, 18000, 38000], [0, 0, 24000, 64000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Split at k=2, choose min cost
14	End: minimum cost for full chain	-	0	3	-	38000	[[0, 6000, 18000, 38000], [0, 0, 24000, 64000], [0, 0, 0, 60000], [0, 0, 0, 0]]	Minimum multiplication cost is 38000
15	Exit	-	-	-	-	-	-	All subproblems solved, final answer found

💡 All subproblems computed, DP table fully filled, minimum cost found for full matrix chain

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 7	After Step 10	After Step 13	Final
m (DP table)	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,6000,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,6000,0,0],[0,0,24000,0],[0,0,0,0],[0,0,0,0]]	[[0,6000,18000,0],[0,0,24000,0],[0,0,0,0],[0,0,0,0]]	[[0,6000,18000,0],[0,0,24000,64000],[0,0,0,60000],[0,0,0,0]]	[[0,6000,18000,38000],[0,0,24000,64000],[0,0,0,60000],[0,0,0,0]]	[[0,6000,18000,38000],[0,0,24000,64000],[0,0,0,60000],[0,0,0,0]]

Key Moments - 3 Insights

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

Because the order of multiplication affects cost, we must check all splits (see steps 6,7,11-13) to find the minimum cost.

Why is the diagonal of the DP table zero?

Diagonal entries represent single matrices (no multiplication needed), so cost is zero (step 1 initialization).

How do we know when to stop filling the DP table?

When chain length reaches the total number of matrices (step 14), the DP table has the minimum cost for the full chain.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the minimum cost computed for multiplying matrices A0 to A2?

A 32000

B 18000

C 24000

D 6000

💡 Hint

Check the 'Cost Computed' and 'DP Table State' columns at step 7.

At which step does the DP table first get a non-zero value for multiplying matrices A1 to A2?

A Step 4

B Step 3

C Step 6

D Step 9

💡 Hint

Look for i=1, j=2 in the execution table and see when cost is computed.

If the dimension of the last matrix changes from 50 to 60, which step's cost calculation will be directly affected?

A Step 3

B Step 13

C Step 9

D Step 7

💡 Hint

Check which steps involve multiplication with the last matrix dimension (50) in the cost formula.

Concept Snapshot

Matrix Chain Multiplication:
- Find minimum cost to multiply matrices in order
- Use DP table m[i][j] for cost of multiplying Ai..Aj
- Fill table by increasing chain length
- Cost = cost_left + cost_right + dims[i]*dims[k+1]*dims[j+1]
- Result in m[0][n-1] after filling
- Avoid brute force by storing subproblem results

Full Transcript

Matrix Chain Multiplication finds the cheapest way to multiply a sequence of matrices. We use a table to store minimum costs for multiplying subchains. Starting with single matrices (cost zero), we increase chain length and calculate costs for all splits. For each subchain, we try all split points, compute cost, and keep the minimum. This process continues until the full chain cost is found. The DP table helps avoid repeated calculations and gives the minimum multiplication cost efficiently.

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 count the total number of matrices in the chain

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

Solution

1. Step 1: Understand the problem context

   The Matrix Chain Multiplication problem aims to multiply a sequence of matrices with the least cost in terms of scalar multiplications.

2. Step 2: Identify the goal

   The goal is to find the order of multiplication that minimizes the total number of scalar multiplications.

3. Final Answer:

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

4. Quick Check:

   Minimum scalar multiplications = Goal [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to initialize the DP table for Matrix Chain Multiplication in Python?

easy

A. dp = [[0 for _ in range(n)] for _ in range(n)]

B. dp = [0] * n

C. dp = [[0] * n]

D. dp = [0 for _ in range(n)]

Solution

1. Step 1: Understand DP table structure

   The DP table for Matrix Chain Multiplication is a 2D table of size n x n to store minimum costs for subproblems.

2. Step 2: Choose correct initialization

   dp = [[0 for _ in range(n)] for _ in range(n)] correctly creates a 2D list with zeros for all n rows and n columns.

3. Final Answer:

   dp = [[0 for _ in range(n)] for _ in range(n)] -> Option A

4. Quick Check:

   2D list initialization = dp with zeros [OK]

Hint: Use nested list comprehensions for 2D DP tables [OK]

Common Mistakes:

• Using one-dimensional list for 2D DP table
• Incorrectly initializing inner lists causing shared references
• Using single list instead of nested lists

3. What will be the output of the following code snippet for p = [10, 20, 30] representing matrix dimensions?

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n-1]

print(matrix_chain_order(p))

medium

A. IndexError

B. 6000

C. None

D. 18000

Solution

1. Step 1: Trace the code execution

   p=[10,20,30], n=2, dp=[[0,0],[0,0]]. l=2, i=0, j=1, dp[0][1]=inf. k=0: cost=dp[0][0]+dp[1][1]+10*20*30=0+0+6000. However, the code tries to access p[j+1] = p[2], which is valid here (p has length 3). So no IndexError here.

2. Step 2: Confirm output

   Return dp[0][1] which is 6000.

3. Final Answer:

   6000 -> Option B

4. Quick Check:

   Cost = p[0]*p[1]*p[2] = 6000 [OK]

Hint: For chain of 2 matrices (n=2), cost is p[0]*p[1]*p[2] [OK]

Common Mistakes:

• Anticipating IndexError on p[j+1]
• Miscalculating cost (e.g., wrong indices)
• Forgetting single k split for l=2

4. Find the bug in this Matrix Chain Multiplication code snippet:

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k]*p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n-1]

medium

A. Return statement is missing

B. DP table initialization is wrong

C. Incorrect multiplication indices in cost calculation

D. Loop ranges are incorrect

Solution

1. Step 1: Review cost calculation formula

   The cost formula should be p[i] * p[k+1] * p[j+1], but code uses p[i] * p[k] * p[j], which is incorrect indexing.

2. Step 2: Identify correct indices

   Matrix dimensions are stored in p, so for multiplying matrices A_i..A_k and A_k+1..A_j, cost uses p[i], p[k+1], and p[j+1].

3. Final Answer:

   Incorrect multiplication indices in cost calculation -> Option C

4. Quick Check:

   Cost formula indices must be p[i], p[k+1], p[j+1] [OK]

Hint: Check dimension indices carefully in cost formula [OK]

Common Mistakes:

• Using p[k] instead of p[k+1]
• Mixing zero-based and one-based indexing
• Ignoring matrix dimension rules

5. Given matrices with dimensions p = [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain?

hard

A. 1510

B. 2010

C. 4050

D. 3500

Solution

1. Step 1: Understand the input and problem

   p has length 7, so there are 6 matrices with dimensions: 5x10, 10x3, 3x12, 12x5, 5x50, 50x6.

2. Step 2: Use dynamic programming to find minimum cost

   By applying the Matrix Chain Multiplication DP algorithm, the minimum cost is calculated as 1510 scalar multiplications.

3. Final Answer:

   1510 -> Option A

4. Quick Check:

   DP minimum scalar multiplications = 1510 [OK]

Hint: Use DP table to store subproblem costs for efficiency [OK]

Common Mistakes:

• Calculating cost manually without DP
• Mixing matrix dimensions incorrectly
• Forgetting to consider all parenthesization options