Matrix Chain Multiplication in DSA Python

Mental Model

We want to find the best way to multiply a chain of matrices so that the total number of multiplications is as small as possible.

Analogy: Imagine you have to multiply several long ropes tied end to end. The order in which you tie and multiply the ropes affects how much effort you spend. Finding the best order saves your energy.

Matrices: A1(10x30) -> A2(30x5) -> A3(5x60)
Goal: Find best way to multiply A1xA2xA3 with least cost.

Dry Run Walkthrough

Input: matrices dimensions: [10, 30, 5, 60] (means A1:10x30, A2:30x5, A3:5x60)

Goal: Find the minimum number of scalar multiplications needed to multiply A1, A2, and A3 in the best order.

Step 1: Calculate cost of multiplying A1 and A2 first, then multiply result with A3

Cost for (A1xA2)xA3 = 10x30x5 + 10x5x60 = 1500 + 3000 = 4500

Why: We multiply A1 and A2 first, which costs 10x30x5, then multiply the result (10x5) with A3 (5x60)

Step 2: Calculate cost of multiplying A2 and A3 first, then multiply A1 with result

Cost for A1x(A2xA3) = 30x5x60 + 10x30x60 = 9000 + 18000 = 27000

Why: We multiply A2 and A3 first, costing 30x5x60, then multiply A1 (10x30) with result (30x60)

Step 3: Compare both costs and choose minimum

Minimum cost = 4500 (from step 1)

Why: Choosing the order (A1xA2)xA3 saves many multiplications compared to A1x(A2xA3)

Result:

Minimum multiplication cost = 4500

Annotated Code

DSA Python

class MatrixChainMultiplication:
    def __init__(self, dims):
        self.dims = dims
        self.n = len(dims) - 1
        self.dp = [[0] * self.n for _ in range(self.n)]

    def compute_min_cost(self):
        for length in range(2, self.n + 1):  # length of chain
            for i in range(self.n - length + 1):
                j = i + length - 1
                self.dp[i][j] = float('inf')
                for k in range(i, j):
                    cost = self.dp[i][k] + self.dp[k + 1][j] + self.dims[i] * self.dims[k + 1] * self.dims[j + 1]
                    if cost < self.dp[i][j]:
                        self.dp[i][j] = cost
        return self.dp[0][self.n - 1]


if __name__ == '__main__':
    dims = [10, 30, 5, 60]
    mcm = MatrixChainMultiplication(dims)
    print(mcm.compute_min_cost())

for length in range(2, self.n + 1):

increase chain length from 2 to n to consider all subproblems

for i in range(self.n - length + 1):

set start index of matrix chain

j = i + length - 1

set end index of matrix chain

self.dp[i][j] = float('inf')

initialize minimum cost for this subchain as infinity

for k in range(i, j):

try all possible split points to find minimum cost

cost = self.dp[i][k] + self.dp[k + 1][j] + self.dims[i] * self.dims[k + 1] * self.dims[j + 1]

calculate cost of splitting at k: cost of left + cost of right + cost of multiplying resulting matrices

if cost < self.dp[i][j]: self.dp[i][j] = cost

update minimum cost if current split is cheaper

return self.dp[0][self.n - 1]

return minimum cost for full chain multiplication

Output

4500

Complexity Analysis

Time: O(n^3) because we check all subchains and all split points for each subchain

Space: O(n^2) because we store minimum costs for all subchains in a 2D table

vs Alternative: Naive approach tries all parenthesizations recursively with exponential time; DP reduces it to polynomial time by storing intermediate results

Edge Cases

Only one matrix (e.g., dims = [10, 20])

No multiplication needed, cost is zero

DSA Python

for length in range(2, self.n + 1):

Two matrices (e.g., dims = [10, 20, 30])

Single multiplication cost calculated directly

DSA Python

for length in range(2, self.n + 1):

Matrices with same dimensions (e.g., dims = [10, 10, 10, 10])

Algorithm still finds minimum cost correctly

DSA Python

for k in range(i, j):

When to Use This Pattern

When you need to find the best order to multiply multiple matrices to minimize operations, use Matrix Chain Multiplication dynamic programming.

Common Mistakes

Mistake: Not initializing dp[i][j] to infinity before checking splits
Fix: Set dp[i][j] = float('inf') before trying all split points to find minimum

Mistake: Incorrectly calculating multiplication cost indices
Fix: Use dims[i] * dims[k+1] * dims[j+1] to calculate cost for multiplying matrices from i to j split at k

Summary

Finds the minimum number of scalar multiplications needed to multiply a chain of matrices.

Use when multiplying multiple matrices where order affects computation cost.

The key is to try all split points and store minimum costs for subchains to avoid repeated work.

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