Matrix Chain Multiplication in DSA Python - Build from Scratch

Matrix Chain Multiplication

📖 Scenario: You work in a company that optimizes the order of multiplying several matrices to save computing time. Different orders of multiplication can take different amounts of time. You want to find the minimum number of scalar multiplications needed to multiply a chain of matrices.

🎯 Goal: Build a program that calculates the minimum number of multiplications needed to multiply a chain of matrices using dynamic programming.

📋 What You'll Learn

Create a list called dimensions with the exact values [40, 20, 30, 10, 30] representing matrix dimensions.

Create a 2D list called dp initialized with zeros for storing minimum multiplication costs.

Use nested for loops with variables length, i, and k to fill the dp table using the matrix chain multiplication formula.

Print the minimum multiplication cost stored in dp[1][n-1].

💡 Why This Matters

🌍 Real World

Matrix chain multiplication optimization is used in computer graphics, scientific computing, and database query optimization to reduce computation time.

💼 Career

Understanding dynamic programming and optimization techniques is valuable for software engineers working on performance-critical applications.

1

Create the matrix dimensions list

Create a list called dimensions with these exact values: [40, 20, 30, 10, 30].

DSA Python

# Create the list dimensions with the given values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Initialize the DP table

Create a 2D list called dp with size n x n where n = len(dimensions), initialized with zeros.

DSA Python

dimensions = [40, 20, 30, 10, 30]
# Initialize dp as a 2D list of zeros with size n x n
# Your code here

Hint

Use list comprehension to create a 2D list filled with zeros.

3

Fill the DP table with minimum multiplication costs

Use nested for loops with variables length, i, and k to fill the dp table. Calculate minimum multiplications using the formula: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + dimensions[i-1]*dimensions[k]*dimensions[j]) for all valid k. Use 1-based indexing for i and j.

DSA Python

dimensions = [40, 20, 30, 10, 30]
n = len(dimensions)
dp = [[0] * n for _ in range(n)]
# Fill dp table using nested loops and the matrix chain multiplication formula
# Your code here

Hint

Use three nested loops: outer for chain length, middle for start index, inner for split point.

4

Print the minimum multiplication cost

Print the minimum multiplication cost stored in dp[1][n-1].

DSA Python

dimensions = [40, 20, 30, 10, 30]
n = len(dimensions)
dp = [[0] * n for _ in range(n)]

for length in range(2, n):
    for i in range(1, n - length + 1):
        j = i + length - 1
        dp[i][j] = float('inf')
        for k in range(i, j):
            cost = dp[i][k] + dp[k+1][j] + dimensions[i-1] * dimensions[k] * dimensions[j]
            if cost < dp[i][j]:
                dp[i][j] = cost

# Print the minimum multiplication cost
# Your code here

Hint

Use print(dp[1][n-1]) to show the result.

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