Matrix Chain Multiplication

Problem Statement

Given a sequence of matrices, find the most efficient way to multiply them together. The order of multiplication matters because matrix multiplication is associative but not commutative. Find the minimum number of scalar multiplications needed.

Example:

• Input: dimensions = [40, 20, 30, 10, 30] (4 matrices: 40×20, 20×30, 30×10, 10×30)
• Output: 26000 (minimum scalar multiplications)

Noob-Friendly Explanation

Imagine you need to multiply 4 matrices: A × B × C × D. You can do it in different orders like (A×B)×(C×D) or ((A×B)×C)×D, etc. Each order takes a different number of multiplications. Some orders are way faster than others! This problem finds the cheapest order. Think of it like figuring out the best order to combine ingredients when cooking — the order you mix things can save a lot of effort.

Approach 1: Brute Force (Recursion)

Intuition

Try every possible place to split the chain of matrices. For each split, recursively find the cost of the left part and the right part, plus the cost of combining them.

Algorithm

1. For matrices from index i to j, try every split point k
2. Cost = cost(i, k) + cost(k+1, j) + dimensions[i-1] × dimensions[k] × dimensions[j]
3. Return the minimum cost among all splits

public class Solution {
    public int matrixChainOrder(int[] dims, int i, int j) {
        // Base case: single matrix, no multiplication needed
        if (i == j) return 0;

        int minCost = Integer.MAX_VALUE;

        // Try every split point
        for (int k = i; k < j; k++) {
            int cost = matrixChainOrder(dims, i, k)
                     + matrixChainOrder(dims, k + 1, j)
                     + dims[i - 1] * dims[k] * dims[j];
            minCost = Math.min(minCost, cost);
        }

        return minCost;
    }

    // Call: matrixChainOrder(dims, 1, n-1) where n = dims.length
}

Complexity Analysis

• Time Complexity: O(2^n) - Exponential due to overlapping subproblems
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Use a 2D table where dp[i][j] stores the minimum cost to multiply matrices from i to j. Fill the table for increasing chain lengths.

Algorithm

1. Create a 2D array dp[n][n] initialized to 0
2. For chain length len from 2 to n-1:
   • For each starting index i, compute ending index j = i + len - 1
   • Try all split points k and store the minimum cost in dp[i][j]
3. Answer is dp[1][n-1]

public class Solution {
    public int matrixChainOrder(int[] dims) {
        int n = dims.length;
        int[][] dp = new int[n][n];

        // len is the chain length
        for (int len = 2; len < n; len++) {
            for (int i = 1; i < n - len + 1; i++) {
                int j = i + len - 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];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[1][n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n^3) - Three nested loops
• Space Complexity: O(n^2) - 2D DP table