Matrix Chain Multiplication in DSA Java - Build from Scratch

Matrix Chain Multiplication

📖 Scenario: You work in a company that processes large sets of matrix multiplications. To optimize the calculations, you want to find the best order to multiply matrices so that the total number of scalar multiplications is minimized.

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

📋 What You'll Learn

Create an integer array called dimensions representing the dimensions of matrices.

Create a 2D integer array called dp to store minimum multiplication costs.

Implement the dynamic programming logic to fill dp with minimum costs.

Print the minimum multiplication cost for the full chain.

💡 Why This Matters

🌍 Real World

Matrix chain multiplication optimization is used in computer graphics, scientific computing, and database query optimization to speed up matrix calculations.

💼 Career

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

1

Create the matrix dimensions array

Create an integer array called dimensions with these exact values: 40, 20, 30, 10, 30.

DSA Java

// Create the dimensions array
// Your code here

Hint

The dimensions array holds the sizes of matrices. For example, matrix 1 is 40x20, matrix 2 is 20x30, and so on.

2

Initialize the DP table

Add a 2D integer array called dp of size dimensions.length by dimensions.length initialized with zeros inside the main method.

DSA Java

public class MatrixChainMultiplication {
    public static void main(String[] args) {
        int[] dimensions = {40, 20, 30, 10, 30};
        // Initialize dp array
        // Your code here
    }
}

Hint

The dp array will store the minimum multiplication costs for matrix chains between indices.

3

Fill the DP table with minimum multiplication costs

Use nested for loops with variables length, i, and k to fill the dp array with minimum multiplication costs using the matrix chain multiplication logic.

DSA Java

public class MatrixChainMultiplication {
    public static void main(String[] args) {
        int[] dimensions = {40, 20, 30, 10, 30};
        int n = dimensions.length;
        int[][] dp = new int[n][n];
        // Fill dp with minimum multiplication costs
        // Your code here
    }
}

Hint

Use dynamic programming to try all possible splits and store the minimum cost in dp[i][j].

4

Print the minimum multiplication cost

Print the minimum multiplication cost stored in dp[1][dimensions.length - 1] using System.out.println.

DSA Java

public class MatrixChainMultiplication {
    public static void main(String[] args) {
        int[] dimensions = {40, 20, 30, 10, 30};
        int n = dimensions.length;
        int[][] dp = new int[n][n];

        for (int length = 2; length < n; length++) {
            for (int i = 1; i < n - length + 1; i++) {
                int j = i + length - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int 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

The minimum multiplication cost for the full chain is stored in dp[1][n-1]. Print it.

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

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

B. To multiply all matrices in the chain directly without optimization

C. To find the maximum number of matrices that can be multiplied

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 cost.

2. Step 2: Identify the cost metric

   The cost is measured by the number of scalar multiplications needed, not just multiplying matrices directly.

3. Final Answer:

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

4. Quick Check:

   Goal = minimum scalar multiplications [OK]

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

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing number of matrices with multiplication cost
• Assuming maximum matrices multiplied 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 Java?

easy

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

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

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

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

Solution

1. Step 1: Understand the dimensions array format

   For n matrices, the dimensions array has length n+1, storing rows of first matrix and columns of each matrix.

2. Step 2: Apply to given matrices

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

3. Final Answer:

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

4. Quick Check:

   Length = 5 for 4 matrices [OK]

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

Common Mistakes:

• Using length equal to number of matrices instead of number+1
• Repeating dimensions unnecessarily
• Including extra unrelated dimensions

3. What will be the output of the following Java code snippet for matrix chain multiplication cost calculation?

int[] dims = {5, 10, 3};
int n = dims.length;
int[][] dp = new int[n][n];
for (int l = 2; l < n; l++) {
  for (int i = 1; i < n - l + 1; i++) {
    int j = i + l - 1;
    dp[i][j] = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
      int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}
System.out.println(dp[1][n-1]);

medium

A. 0

B. 75

C. 150

D. Syntax Error

Solution

1. Step 1: Understand the input matrices

   Dimensions: 5x10 and 10x3 matrices. Only one way to multiply.

2. Step 2: Calculate multiplication cost

   Cost = 5*10*3 = 150 scalar multiplications.

3. Final Answer:

   150 -> Option C

4. Quick Check:

   5*10*3 = 150 [OK]

Hint: Multiply dims[i-1]*dims[k]*dims[j] for cost [OK]

Common Mistakes:

• Confusing indices in cost calculation
• Assuming zero cost for single multiplication
• Syntax errors from incorrect loops

4. Identify the error in the following Java code snippet for matrix chain multiplication:

int[] dims = {2, 3, 4};
int n = dims.length;
int[][] dp = new int[n][n];
for (int l = 2; l <= n; l++) {
  for (int i = 1; i <= n - l + 1; i++) {
    int j = i + l - 1;
    dp[i][j] = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
      int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}
System.out.println(dp[1][n-1]);

medium

A. Loop condition l <= n causes ArrayIndexOutOfBoundsException

B. Incorrect cost calculation formula

C. dp array should be one-dimensional

D. Missing initialization of dp array

Solution

1. Step 1: Analyze loop bounds

   Outer loop runs l from 2 to n inclusive, but dp indices go up to n-1.

2. Step 2: Identify index error

   When l = n, j = i + l - 1 can exceed dp array size causing ArrayIndexOutOfBoundsException.

3. Final Answer:

   Loop condition l <= n causes ArrayIndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop bound off by one causes index error [OK]

Hint: Check loop bounds carefully to avoid index errors [OK]

Common Mistakes:

• Using <= n instead of < n for loop limit
• Ignoring array size limits
• Misunderstanding dp array dimensions

5. Given matrices with dimensions {40, 20, 30, 10, 30}, what is the minimum number of scalar multiplications needed to multiply the entire chain?

hard

A. 30000

B. 26000

C. 18000

D. 35000

Solution

1. Step 1: Understand matrix dimensions

   Matrices: 40x20, 20x30, 30x10, 10x30.

2. Step 2: Calculate minimum cost using dynamic programming

   Possible parenthesizations and costs:
   - ((40x20)x30)x(10x30):
   Cost1 = 40*20*30=24000 + 40*30*10=12000 + 0 = 36000 (too high)
   - (40x(20x30))x(10x30):
   Cost2 = 20*30*10=6000 + 40*20*10=8000 + 40*10*30=12000 = 26000 (minimum)

3. Final Answer:

   26000 -> Option B

4. Quick Check:

   Minimum scalar multiplications = 26000 [OK]

Hint: Try all splits and pick minimum cost [OK]

Common Mistakes:

• Calculating cost for only one parenthesization
• Mixing up matrix dimensions order
• Ignoring intermediate multiplication costs