Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Matrix Chain Multiplication

HARDProblemSolveExternal Links

Description

Given the dimensions of a sequence of matrices in an array arr[], where the i-th matrix has dimensions arr[i-1] × arr[i] (for i ≥ 1), find the most efficient way to multiply these matrices together such that the total number of scalar multiplications is minimized.

The problem is not to actually perform the multiplications, but to decide the order (parenthesization) in which to multiply the matrices. Matrix multiplication is associative — the result is the same regardless of how you parenthesize — but the number of scalar multiplications changes dramatically depending on the grouping.

When a matrix of size m × n is multiplied with a matrix of size n × p, it produces a matrix of size m × p and requires m × n × p scalar multiplications.

Return the minimum number of scalar multiplications needed to compute the product of the entire chain.

Examples

Example 1

Input: arr = [2, 1, 3, 4]

Output: 20

Explanation: There are 3 matrices: M1 (2×1), M2 (1×3), M3 (3×4). Two possible parenthesizations:

  • ((M1 × M2) × M3): Cost of M1×M2 = 2×1×3 = 6 (produces 2×3 matrix), then (result)×M3 = 2×3×4 = 24. Total = 6 + 24 = 30.
  • (M1 × (M2 × M3)): Cost of M2×M3 = 1×3×4 = 12 (produces 1×4 matrix), then M1×(result) = 2×1×4 = 8. Total = 12 + 8 = 20.

The minimum is 20, achieved by the second parenthesization.

Example 2

Input: arr = [1, 2, 3, 4, 3]

Output: 30

Explanation: There are 4 matrices: M1 (1×2), M2 (2×3), M3 (3×4), M4 (4×3). The optimal parenthesization is ((M1 × M2) × M3) × M4:

  • M1 × M2 = 1×2×3 = 6 (produces 1×3)
  • (M1M2) × M3 = 1×3×4 = 12 (produces 1×4)
  • ((M1M2)M3) × M4 = 1×4×3 = 12 (produces 1×3)
  • Total = 6 + 12 + 12 = 30.

Example 3

Input: arr = [3, 4]

Output: 0

Explanation: There is only one matrix (3×4). No multiplication is needed, so the cost is 0.

Constraints

  • 2 ≤ arr.size() ≤ 100
  • 1 ≤ arr[i] ≤ 200

Editorial

Brute Force

Intuition

The most natural approach is to try every possible way of parenthesizing the chain and pick the one with the fewest multiplications.

Think of it this way: you have a row of matrices to multiply. At some point, you must make a "last split" — a point where you divide the entire chain into a left group and a right group, multiply each group internally, then multiply the two results together. Where you place that split matters enormously.

For example, with matrices M1, M2, M3, M4, the last split could be:

  • After M1: (M1) × (M2 × M3 × M4)
  • After M2: (M1 × M2) × (M3 × M4)
  • After M3: (M1 × M2 × M3) × (M4)

Each split creates two smaller subproblems — "what's the cheapest way to multiply the left group?" and "what's the cheapest way to multiply the right group?" We solve these recursively, add the cost of multiplying the two resulting matrices, and pick the split that gives the lowest total.

We represent the chain using index range [i, j] in the dimensions array, where the matrices in this range are arr[i]×arr[i+1], arr[i+1]×arr[i+2], ..., arr[j-1]×arr[j]. To split at position k (where i < k < j), the left subchain is [i, k] and the right subchain is [k, j]. The cost of the final multiplication is arr[i] × arr[k] × arr[j], because the left product is an arr[i]×arr[k] matrix and the right product is an arr[k]×arr[j] matrix.

Step-by-Step Explanation

Let's trace through with arr = [2, 1, 3, 4] (matrices: M1=2×1, M2=1×3, M3=3×4):

Step 1: Call minCost(0, 3). We need to find the minimum cost for the full chain [0..3].

  • Try k=1: left=[0,1] (M1), right=[1,3] (M2×M3), merge cost = arr[0]×arr[1]×arr[3] = 2×1×4 = 8
  • Try k=2: left=[0,2] (M1×M2), right=[2,3] (M3), merge cost = arr[0]×arr[2]×arr[3] = 2×3×4 = 24

Step 2: Solve subproblem minCost(0, 1). Range has only one matrix (M1). Cost = 0.

Step 3: Solve subproblem minCost(1, 3) — matrices M2 (1×3) and M3 (3×4).

  • Only one split: k=2. left=[1,2] cost=0, right=[2,3] cost=0.
  • Merge cost = arr[1]×arr[2]×arr[3] = 1×3×4 = 12.
  • Total = 0 + 0 + 12 = 12.

Step 4: Back in minCost(0, 3), k=1 gives: 0 + 12 + 8 = 20.

Step 5: Solve subproblem minCost(0, 2) — matrices M1 (2×1) and M2 (1×3).

  • Only one split: k=1. left=[0,1] cost=0, right=[1,2] cost=0.
  • Merge cost = arr[0]×arr[1]×arr[2] = 2×1×3 = 6.
  • Total = 0 + 0 + 6 = 6.

Step 6: Solve subproblem minCost(2, 3). Only one matrix (M3). Cost = 0.

Step 7: Back in minCost(0, 3), k=2 gives: 6 + 0 + 24 = 30.

Step 8: Compare all splits: k=1 → 20, k=2 → 30. Minimum = 20.

Result: Minimum multiplication cost = 20.

Brute Force — Recursive Exploration of All Parenthesizations — Watch how the recursion explores every possible split point for the chain [0..3], branching into left and right subproblems, then combining costs to find the minimum.

Algorithm

  1. Define a recursive function minCost(i, j) where i and j are indices in the dimensions array arr[]. The subproblem represents multiplying matrices from index i to j.
  2. Base case: If i + 1 == j, there is only one matrix — return 0 (no multiplication needed).
  3. For each possible split point k from i+1 to j-1:
    • Recursively compute leftCost = minCost(i, k)
    • Recursively compute rightCost = minCost(k, j)
    • Compute mergeCost = arr[i] × arr[k] × arr[j]
    • Track the minimum of leftCost + rightCost + mergeCost across all k
  4. Return the minimum cost found.
  5. The answer is minCost(0, n-1) where n is the length of arr[].

Code

#include <bits/stdc++.h>
using namespace std;

int minCostRec(vector<int>& arr, int i, int j) {
    // Base case: single matrix, no multiplication
    if (i + 1 == j)
        return 0;
    
    int res = INT_MAX;
    
    // Try every possible split point
    for (int k = i + 1; k < j; k++) {
        int cost = minCostRec(arr, i, k)
                 + minCostRec(arr, k, j)
                 + arr[i] * arr[k] * arr[j];
        res = min(res, cost);
    }
    
    return res;
}

int matrixMultiplication(vector<int>& arr) {
    int n = arr.size();
    return minCostRec(arr, 0, n - 1);
}
import sys

def matrixMultiplication(arr):
    n = len(arr)
    
    def minCostRec(i, j):
        # Base case: single matrix
        if i + 1 == j:
            return 0
        
        res = sys.maxsize
        
        # Try every split point
        for k in range(i + 1, j):
            cost = (minCostRec(i, k)
                   + minCostRec(k, j)
                   + arr[i] * arr[k] * arr[j])
            res = min(res, cost)
        
        return res
    
    return minCostRec(0, n - 1)
class Solution {
    static int minCostRec(int[] arr, int i, int j) {
        // Base case: single matrix
        if (i + 1 == j)
            return 0;
        
        int res = Integer.MAX_VALUE;
        
        // Try every split point
        for (int k = i + 1; k < j; k++) {
            int cost = minCostRec(arr, i, k)
                     + minCostRec(arr, k, j)
                     + arr[i] * arr[k] * arr[j];
            res = Math.min(res, cost);
        }
        
        return res;
    }
    
    static int matrixMultiplication(int[] arr) {
        int n = arr.length;
        return minCostRec(arr, 0, n - 1);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each level, we try up to n-2 split points, and each split creates two subproblems that can themselves branch further. The number of possible parenthesizations is the (n-2)th Catalan number, which grows exponentially — roughly O(4^n / n^(3/2)). In practice, the recursion explores an exponential number of overlapping subproblems.

Space Complexity: O(n)

The recursion depth is at most n-1 (one level per matrix boundary). Each stack frame uses O(1) space, so the call stack uses O(n) total.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity. With n up to 100, even O(2^n) is astronomically large — far beyond what any computer can handle in a reasonable time.

The root cause is overlapping subproblems. Consider a chain of 5 matrices. When we split at k=2, we solve minCost(0,2) and minCost(2,4). When we split at k=3, we solve minCost(0,3) which internally also solves minCost(0,2). The subproblem minCost(0,2) gets recomputed from scratch each time it's needed.

Key insight: The state of any subproblem is fully determined by just two numbers: the start index i and end index j. There are only O(n²) unique (i, j) pairs. If we cache (memoize) the result after computing each pair once, we eliminate all redundant work. Each cached subproblem takes O(n) work to compute (trying all split points), giving O(n³) total — a massive improvement over exponential.

Optimal Approach - Memoization (Top-Down DP)

Intuition

The recursive structure from the brute force is already correct — we just need to avoid recomputing the same subproblems. We add a memoization table memo[i][j] that stores the answer for each subchain [i..j] once computed.

Before recursing into any subproblem, we first check: "Have I already solved minCost(i, j)?" If yes, return the cached answer instantly. If no, compute it, store the result, then return.

Think of it like solving a jigsaw puzzle. The first time you figure out how a cluster of pieces fits together, you glue them. Next time you need that cluster, you grab the pre-assembled piece instead of re-solving it from scratch.

The state space has two dimensions:

  • i ranges from 0 to n-2 (start of subchain)
  • j ranges from i+1 to n-1 (end of subchain)

Total unique subproblems: roughly n²/2. Each subproblem tries at most n-2 split points, doing O(1) work per split. Total work: O(n²) subproblems × O(n) splits each = O(n³).

Step-by-Step Explanation

Let's trace with arr = [2, 1, 3, 4] using memoization:

Step 1: Call minCost(0, 3). memo is empty. Try k=1 first.

Step 2: Need minCost(0, 1). Base case (single matrix) → 0. Cache memo[0][1] = 0.

Step 3: Need minCost(1, 3). Not cached. Try k=2.

  • minCost(1, 2) = 0 (base case, cached).
  • minCost(2, 3) = 0 (base case, cached).
  • Merge = 1×3×4 = 12. Total = 0 + 0 + 12 = 12.
  • Cache memo[1][3] = 12.

Step 4: Back in minCost(0, 3): k=1 gives 0 + 12 + 8 = 20. Record best = 20.

Step 5: Try k=2. Need minCost(0, 2). Not cached.

  • Only split k=1: minCost(0,1)=0 (CACHE HIT!), minCost(1,2)=0 (CACHE HIT!).
  • Merge = 2×1×3 = 6. Total = 6.
  • Cache memo[0][2] = 6.

Step 6: Need minCost(2, 3) = 0 (CACHE HIT!).

Step 7: k=2 gives 6 + 0 + 24 = 30. Compare: 30 > 20. Best stays 20.

Step 8: Cache memo[0][3] = 20. Return 20.

Result: Only 6 unique subproblems computed instead of exponential branching.

Memoization — Caching Subproblem Results as They're Computed — Watch how the memo table fills as the recursion discovers and caches subproblem results. Each cell memo[i][j] stores the minimum cost to multiply the chain from index i to j.

Algorithm

  1. Create a 2D memoization table memo[n][n] initialized to -1 (uncomputed).
  2. Define minCost(i, j):
    • If i + 1 == j, return 0 (base case: single matrix).
    • If memo[i][j] != -1, return the cached value.
    • For each split point k from i+1 to j-1:
      • Compute cost = minCost(i, k) + minCost(k, j) + arr[i] * arr[k] * arr[j]
      • Track the minimum cost.
    • Store the minimum in memo[i][j] and return it.
  3. Return minCost(0, n-1).

Code

#include <bits/stdc++.h>
using namespace std;

int minCostRec(vector<int>& arr, int i, int j,
               vector<vector<int>>& memo) {
    if (i + 1 == j)
        return 0;
    
    if (memo[i][j] != -1)
        return memo[i][j];
    
    int res = INT_MAX;
    
    for (int k = i + 1; k < j; k++) {
        int cost = minCostRec(arr, i, k, memo)
                 + minCostRec(arr, k, j, memo)
                 + arr[i] * arr[k] * arr[j];
        res = min(res, cost);
    }
    
    return memo[i][j] = res;
}

int matrixMultiplication(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> memo(n, vector<int>(n, -1));
    return minCostRec(arr, 0, n - 1, memo);
}
import sys

def matrixMultiplication(arr):
    n = len(arr)
    memo = [[-1] * n for _ in range(n)]
    
    def minCostRec(i, j):
        if i + 1 == j:
            return 0
        
        if memo[i][j] != -1:
            return memo[i][j]
        
        res = sys.maxsize
        
        for k in range(i + 1, j):
            cost = (minCostRec(i, k)
                   + minCostRec(k, j)
                   + arr[i] * arr[k] * arr[j])
            res = min(res, cost)
        
        memo[i][j] = res
        return res
    
    return minCostRec(0, n - 1)
class Solution {
    static int minCostRec(int[] arr, int i, int j, int[][] memo) {
        if (i + 1 == j)
            return 0;
        
        if (memo[i][j] != -1)
            return memo[i][j];
        
        int res = Integer.MAX_VALUE;
        
        for (int k = i + 1; k < j; k++) {
            int cost = minCostRec(arr, i, k, memo)
                     + minCostRec(arr, k, j, memo)
                     + arr[i] * arr[k] * arr[j];
            res = Math.min(res, cost);
        }
        
        return memo[i][j] = res;
    }
    
    static int matrixMultiplication(int[] arr) {
        int n = arr.length;
        int[][] memo = new int[n][n];
        for (int[] row : memo)
            java.util.Arrays.fill(row, -1);
        return minCostRec(arr, 0, n - 1, memo);
    }
}

Complexity Analysis

Time Complexity: O(n³)

There are O(n²) unique subproblems — each defined by a pair (i, j) where 0 ≤ i < j ≤ n-1. For each subproblem, we iterate over up to O(n) split points. Each split does O(1) work (addition and comparison). Total: O(n²) subproblems × O(n) work each = O(n³).

Space Complexity: O(n²)

The memoization table memo[n][n] uses O(n²) space. The recursion stack can go up to O(n) depth. Total space: O(n²) + O(n) = O(n²).