Matrix Chain Multiplication in DSA C++

Mental Model

We want to multiply a chain of matrices with the least number of multiplications by choosing the best order to multiply them.

Analogy: Imagine you have several long ropes to tie together. The order in which you tie them affects how much effort you spend. Choosing the best order saves effort.

Matrices: A1[10x30] -> A2[30x5] -> A3[5x60]
Goal: Find best way to multiply A1xA2xA3 with minimum 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 A1xA2xA3

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 multiplications, then multiply the result with A3

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

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

Why: We multiply A2 and A3 first, which costs 30x5x60 multiplications, then multiply A1 with the result

Step 3: Compare both costs and choose the 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 C++

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int matrixChainMultiplication(const vector<int>& dims) {
    int n = dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // l is chain length
    for (int l = 2; l <= n; ++l) {
        for (int i = 0; i <= n - l; ++i) {
            int j = i + l - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {
                int 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;
                }
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    vector<int> dims = {10, 30, 5, 60};
    cout << matrixChainMultiplication(dims) << "\n";
    return 0;
}

for (int l = 2; l <= n; ++l) {

iterate over chain lengths from 2 to n

for (int i = 0; i <= n - l; ++i) {

set start index of the chain

int j = i + l - 1;

set end index of the chain

dp[i][j] = INT_MAX;

initialize minimum cost for this subchain

for (int k = i; k < j; ++k) {

try all possible split points

int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];

calculate cost of splitting at k

if (cost < dp[i][j]) { dp[i][j] = cost; }

update minimum cost if current split is cheaper

Output

4500

Complexity Analysis

Time: O(n^3) because we check all pairs and all split points for chains of length n

Space: O(n^2) for storing minimum costs of all subchains in dp table

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

Edge Cases

Only one matrix (dims size 2)

No multiplication needed, cost is zero

DSA C++

dp[i][j] = 0 for i == j (implicit as dp initialized with 0)

Two matrices (dims size 3)

Only one way to multiply, cost is dims[0]*dims[1]*dims[2]

DSA C++

for (int l = 2; l <= n; ++l) handles chain length 2

When to Use This Pattern

When asked to find the best order to multiply matrices or combine operations with associative property to minimize cost, use Matrix Chain Multiplication dynamic programming.

Common Mistakes

Mistake: Using wrong indices for dimensions when calculating cost
Fix: Use dims[i] * dims[k+1] * dims[j+1] to correctly get matrix dimensions for multiplication cost

Mistake: Not initializing dp[i][j] to a large number before finding minimum
Fix: Set dp[i][j] = INT_MAX before checking splits to find minimum cost

Summary

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

Use when you want to multiply multiple matrices efficiently by choosing the best multiplication order.

The key insight is that the problem can be broken into smaller subproblems and solved with dynamic programming.

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 find the minimum number of scalar multiplications needed to multiply a chain of matrices

D. To count the total number of matrices in the chain

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices to minimize computation.

2. Step 2: Identify the correct goal

   The goal is to minimize the number of scalar multiplications, not just multiply or count matrices.

3. Final Answer:

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

4. Quick Check:

   Goal = Minimum multiplications [OK]

Hint: Remember: minimize multiplication cost, not just multiply [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare the dimensions array for 4 matrices with dimensions 10x20, 20x30, 30x40, and 40x50 in C++?

easy

A. int dims[] = {10, 20, 30, 40, 50};

B. int dims[] = {10, 20, 30, 40};

C. int dims[] = {10, 20, 30, 40, 50, 60};

D. int dims[] = {20, 30, 40, 50};

Solution

1. Step 1: Understand the dimensions array format

   For n matrices, the dimensions array has n+1 elements representing rows and columns of each matrix.

2. Step 2: Apply to given matrices

   For matrices 10x20, 20x30, 30x40, 40x50, dims = {10, 20, 30, 40, 50}.

3. Final Answer:

   int dims[] = {10, 20, 30, 40, 50}; -> Option A

4. Quick Check:

   Dimensions array length = number of matrices + 1 [OK]

Hint: Dimensions array length = matrices count + 1 [OK]

Common Mistakes:

• Using fewer elements than needed in the dimensions array
• Including extra unrelated numbers
• Confusing matrix dimensions order

3. What is the output of the following C++ code snippet for Matrix Chain Multiplication cost calculation?

int dims[] = {5, 10, 3, 12, 5};
int n = 4;
int m[5][5] = {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] = 1000000;
    for (int k = i; k < j; k++) {
      int cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j]) m[i][j] = cost;
    }
  }
}
std::cout << m[1][n] << std::endl;

medium

A. 270

B. 150

C. 201

D. 405

Solution

1. Step 1: Understand matrix dimensions and indices

   Dimensions: 5x10, 10x3, 3x12, 12x5; n=4 matrices; m[i][j] stores min cost from i to j.

2. Step 2: Calculate minimum multiplication cost

   Length 2: m[1][2]=150, m[2][3]=360, m[3][4]=180
   Length 3: m[1][3]=min(0+360+600,150+0+180)=330; m[2][4]=min(0+180+150,360+0+600)=330
   Length 4: m[1][4]=min(0+330+250,150+180+75,330+0+300)=405

3. Final Answer:

   405 -> Option D

4. Quick Check:

   Minimum cost = 405 [OK]

Hint: Trace splits and pick minimum cost [OK]

Common Mistakes:

• Mixing up indices i, j, k
• Incorrect cost formula application
• Forgetting to initialize m[i][j] to max

4. Identify the error in the following C++ code snippet for Matrix Chain Multiplication and choose the correct fix:

int dims[] = {40, 20, 30, 10, 30};
int n = 4;
int m[5][5];
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] = 0;
    for (int k = i; k < j; k++) {
      int cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j])
        m[i][j] = cost;
    }
  }
}

medium

A. Change dims indexing to dims[i-1]*dims[k]*dims[j]

B. Initialize m[i][j] to INT_MAX instead of 0 before inner loop

C. Start i loop from 0 instead of 1

D. Remove the if condition inside the inner loop

Solution

1. Step 1: Identify initialization mistake

   m[i][j] is set to 0 before checking for minimum cost, which causes incorrect comparisons.

2. Step 2: Correct initialization

   m[i][j] should be initialized to a very large number (INT_MAX) to find minimum cost correctly.

3. Final Answer:

   Initialize m[i][j] to INT_MAX instead of 0 before inner loop -> Option B

4. Quick Check:

   Use INT_MAX to find minimum cost [OK]

Hint: Initialize costs to max before minimizing [OK]

Common Mistakes:

• Setting m[i][j] to 0 instead of INT_MAX
• Incorrect dims indexing causing wrong cost
• Ignoring initialization leading to wrong min

5. Given matrices with dimensions 10x15, 15x20, 20x25, and 25x30, what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the Matrix Chain Multiplication approach.

hard

A. 15500

B. 15000

C. 13000

D. 11250

Solution

1. Step 1: List matrix dimensions and possible splits

   Matrices: A1(10x15), A2(15x20), A3(20x25), A4(25x30). dims=[10,15,20,25,30]. Calculate costs for chain length 2 to 4.

2. Step 2: Calculate minimum costs for each subchain

   Length 2: m[1][2]=10*15*20=3000; m[2][3]=15*20*25=7500; m[3][4]=20*25*30=15000
   Length 3: m[1][3]=min(0+7500+10*15*25=11250, 3000+0+10*20*25=8000)=8000;
   m[2][4]=min(0+15000+15*20*30=24000, 7500+0+15*25*30=18750)=18750
   Length 4: m[1][4]=min(0+18750+10*15*30=23250, 3000+15000+10*20*30=24000, 8000+0+10*25*30=15500)=15500

3. Final Answer:

   15500 -> Option A

4. Quick Check:

   Minimum scalar multiplications = 15500 [OK]

Hint: Calculate costs for smaller chains first, then combine [OK]

Common Mistakes:

• Incorrectly calculating subproblems costs
• Mixing up matrix dimensions in cost formula
• Not checking all split points k