Matrix chain multiplication

Identification:

Whenever we need to find the answer to a large problem such that the problem can be broken into subproblems and the final answer varies due to the order in which the subproblems are solved, we can think in terms of partition DP.

Matrix Chain Multiplication:

Let us first understand the problem of matrix chain multiplication. In order to understand the problem we need to first understand the rules of matrix multiplication:

Two matrices A1 and A2 of dimensions [p x q] and [r x s] can only be multiplied if and only if q=r.

The total number of multiplications required to multiply A1 and A2 are: p*q*s

Understanding:

As this problem of matrix multiplication solves one big problem ( minimum operations to get A1.A2….An) and the answer varies in the order the subproblems are being solved, we can identify this problem of pattern partition DP.

Rules to solve the problem of partition DP:

Start with the entire block/array and mark it with i,j: We are given an array, which can be represented by 'i' and 'j' as shown in the image below.

Try out all partitions:

As we can see 3 partitions are possible, to try all three partitions, initialize a for loop starting from 'i' and ending at (j-1), (1 to 3) in this case. The two partitions will be f(i,k) and f(k+1,j).

Base Case: If i==j, it means we are interested in a single matrix and no operation is required to multiply it so return 0.
Run the best possible answer of the two partitions: Answer that comes after dividing the problem into two subproblems and solving them recursively. Let's understand this by the help of an example.

As there are only two matrices, we can say that only one partition is possible at k=1, when we do this partition, we see that the two partitions made are f(1,1) and f(2,2) (by f(i,k) and f(k+1,j) therefore we hit the base condition in both of these subcases which return 0.

Now, we know that the subproblems/partitions give us 0 operations, but we still have some work to do. The partition f(i,k) gives us a resultant matrix of dimensions [i -1 x k] and the partition f(k+1,j) gives us a resultant matrix of dimensions [k,j]. Therefore we need to count the number of operations for our two partitions (k=1) as shown:

Now, this is at one partition, in general, we need to calculate this answer of every partition and return the minimum as the answer.

To summarize:

Represent the entire array by two indexes i and j. In this question i =1 and j = n. We need to find f(i,j).
Maintain a 'mini' variable to get the minimum answer.>/li>
Set a for loop to find the answer( variable k) from i to j-1. In every iteration find the answer, with the formula discussed above and compare it with the 'mini' value.
Finally, return the 'mini' variable as the answer.

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

class Solution{
private:
    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    int func(vector<int>& arr, int i, int j) {
    
        /* Base case: When there is only one
        matrix, no multiplication is needed*/
        if (i == j)
            return 0;
    
        int mini = INT_MAX; 
    
        // Partition the matrices between i and j
        for (int k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying matrices 
            from i to k and from k+1 to j and add cost
            of multiplying the two resulting matrices*/
            int ans = func(arr, i, k) + func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
        
            // Update the minimum cost
            mini = min(mini, ans);
        }
        // Return the minimum cost found
        return mini; 
    }
public:
    /* Function to set up the parameters
    and call the recursive function*/
    int matrixMultiplication(vector<int>& nums) {
        int N = nums.size();
        
        // Starting index of the matrix chain
        int i = 1; 
        
        // Ending index of the matrix chain
        int j = N - 1; 
    
        // Call the recursive function
        return func(nums, i, j);
    }
};

int main() {
    vector<int> arr = {10, 20, 30, 40, 50}; 
    
    //Create an instance of Solution class
    Solution sol;
    
    // Print the result
    cout << "The minimum number of operations is " << sol.matrixMultiplication(arr);
    
    return 0;
}
import java.util.*;

class Solution {
    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    private int func(int[] arr, int i, int j) {
        /* Base case: When there is only one
        matrix, no multiplication is needed*/
        if (i == j)
            return 0;

        int mini = Integer.MAX_VALUE;

        // Partition the matrices between i and j
        for (int k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying matrices 
            from i to k and from k+1 to j and add cost
            of multiplying the two resulting matrices*/
            int ans = func(arr, i, k) + func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
            
            // Update the minimum cost
            mini = Math.min(mini, ans);
        }
        // Return the minimum cost found
        return mini;
    }

    /* Function to set up the parameters
    and call the recursive function*/
    public int matrixMultiplication(int[] nums) {
        int N = nums.length;

        // Starting index of the matrix chain
        int i = 1;
        
        // Ending index of the matrix chain
        int j = N - 1;

        // Call the recursive function
        return func(nums, i, j);
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the result
        System.out.println("The minimum number of operations is " + sol.matrixMultiplication(arr));
    }
}
class Solution:
    """ Recursive function to compute the 
    minimum cost of matrix multiplication"""
    def func(self, arr, i, j):
        """ Base case: When there is only one 
        matrix, no multiplication is needed"""
        if i == j:
            return 0

        mini = float('inf')

        # Partition the matrices between i and j
        for k in range(i, j):
            """ Compute the cost of multiplying matrices 
            from i to k and from k+1 to j and add cost
            of multiplying the two resulting matrices"""
            ans = self.func(arr, i, k) + self.func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j]
            
            # Update the minimum cost
            mini = min(mini, ans)

        return mini

    def matrixMultiplication(self, nums):
        N = len(nums)

        # Starting index of the matrix chain
        i = 1
        
        # Ending index of the matrix chain
        j = N - 1

        # Call the recursive function
        return self.func(nums, i, j)

if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50]
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the result
    print("The minimum number of operations is", sol.matrixMultiplication(arr))
class Solution {

    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    func(arr, i, j) {
        /* Base case: When there is only one
        matrix, no multiplication is needed*/
        if (i === j) return 0;

        let mini = Infinity;

        // Partition the matrices between i and j
        for (let k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying matrices 
            from i to k and from k+1 to j and add cost
            of multiplying the two resulting matrices*/
            const ans = this.func(arr, i, k) + this.func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
            
            // Update the minimum cost
            mini = Math.min(mini, ans);
        }
        return mini;
    }

    /* Function to set up the parameters
    and call the recursive function*/
    matrixMultiplication(nums) {
        const N = nums.length;

        // Starting index of the matrix chain
        const i = 1;
        
        // Ending index of the matrix chain
        const j = N - 1;

        // Call the recursive function
        return this.func(nums, i, j);
    }
}

const arr = [10, 20, 30, 40, 50];

// Create an instance of Solution class
const sol = new Solution();

// Print the result
console.log(`The minimum number of operations is ${sol.matrixMultiplication(arr)}`);

Complexity Analysis:

Time Complexity: Exponential.

Space Complexity: O(N), As we are using auxiliary stack space.

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n][n]: As there are two changing parameters in the recursive solution, 'i' and 'j'. The maximum value 'i' and 'j' can attain is (n), where n is the size of array. Therefore, we need 2D dp array.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

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

class Solution{
private:
    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    int func(vector<int>& arr, int i, int j, vector<vector<int>>& dp) {
    
        /* Base case: When there is only one
        matrix, no multiplication is needed*/
        if (i == j)
            return 0;
        
        //Check if the subproblem is already calculated    
        if(dp[i][j]!=-1)
        return dp[i][j];
    
        int mini = INT_MAX; 
    
        // Partition the matrices between i and j
        for (int k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying matrices 
            from i to k and from k+1 to j and add cost
            of multiplying the two resulting matrices*/
            int ans = func(arr, i, k, dp) + func(arr, k + 1, j, dp) + arr[i - 1] * arr[k] * arr[j];
        
            // Update the minimum cost
            mini = min(mini, ans);
        }
        // Store and return the minimum cost found
        return dp[i][j] = mini; 
    }
public:
    /* Function to set up the parameters
    and call the recursive function*/
    int matrixMultiplication(vector<int>& nums) {
        int N = nums.size();
        
        // Starting index of the matrix chain
        int i = 1; 
        
        // Ending index of the matrix chain
        int j = N - 1; 
        
        vector<vector<int>> dp(N,vector<int>(N,-1));
        
        // Call the recursive function
        return func(nums, i, j, dp);
    }
};

int main() {
    vector<int> arr = {10, 20, 30, 40, 50}; 
    
    //Create an instance of Solution class
    Solution sol;
    
    // Print the result
    cout << "The minimum number of operations is " << sol.matrixMultiplication(arr);
    
    return 0;
}
import java.util.*;

class Solution {
    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    private int func(int[] arr, int i, int j, int[][] dp) {
        /* Base case: When there is only one 
        matrix, no multiplication is needed*/
        if (i == j)
            return 0;
        
        // Check if the subproblem is already calculated
        if (dp[i][j] != -1)
            return dp[i][j];
        
        int mini = Integer.MAX_VALUE;

        // Partition the matrices between i and j
        for (int k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying 
            matrices from i to k and from k+1 to j*/
            int ans = func(arr, i, k, dp) + func(arr, k + 1, j, dp) + arr[i - 1] * arr[k] * arr[j];
            
            // Update the minimum cost
            mini = Math.min(mini, ans);
        }
        // Store and return the minimum cost found
        dp[i][j] = mini;
        return mini;
    }

    /* Function to set up the parameters
    and call the recursive function*/
    public int matrixMultiplication(int[] nums) {
        int N = nums.length;

        // Starting index of the matrix chain
        int i = 1;
        
        // Ending index of the matrix chain
        int j = N - 1;

        int[][] dp = new int[N][N];
        for (int[] row : dp)
            Arrays.fill(row, -1);

        // Call the recursive function
        return func(nums, i, j, dp);
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the result
        System.out.println("The minimum number of operations is " + sol.matrixMultiplication(arr));
    }
}
import sys

class Solution:
    def __init__(self):
        self.dp = None
    """ Recursive function to compute the 
    minimum cost of matrix multiplication"""
    def func(self, arr, i, j):
        """ Base case: When there is only one 
        matrix, no multiplication is needed"""
        if i == j:
            return 0
        
        # Check if the subproblem is already calculated
        if self.dp[i][j] != -1:
            return self.dp[i][j]

        mini = float('inf')

        # Partition the matrices between i and j
        for k in range(i, j):
            """ Compute the cost of multiplying
            matrices from i to k and from k+1 to j"""
            ans = self.func(arr, i, k) + self.func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j]
            
            # Update the minimum cost
            mini = min(mini, ans)

        # Store and return the minimum cost found
        self.dp[i][j] = mini
        return mini

    """ Function to set up the parameters 
    and call the recursive function"""
    def matrixMultiplication(self, arr):
        N = len(arr)

        # Starting index of the matrix chain
        i = 1
        
        # Ending index of the matrix chain
        j = N - 1

        self.dp = [[-1] * N for _ in range(N)]

        # Call the recursive function
        return self.func(arr, i, j)

if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50]
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the result
    print("The minimum number of operations is", sol.matrixMultiplication(arr))
class Solution {
    constructor() {
        this.dp = null;
    }

    /* Recursive function to compute the 
    minimum cost of matrix multiplication*/
    func(arr, i, j) {
        /* Base case: When there is only one
        matrix, no multiplication is needed*/
        if (i === j) return 0;
        
        // Check if the subproblem is already calculated
        if (this.dp[i][j] !== -1) return this.dp[i][j];

        let mini = Infinity;

        // Partition the matrices between i and j
        for (let k = i; k <= j - 1; k++) {
            /* Compute the cost of multiplying 
            matrices from i to k and from k+1 to j*/
            const ans = this.func(arr, i, k) + this.func(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
            
            // Update the minimum cost
            mini = Math.min(mini, ans);
        }

        // Store and return the minimum cost found
        this.dp[i][j] = mini;
        return mini;
    }

    /* Function to set up the parameters 
    and call the recursive function*/
    matrixMultiplication(nums) {
        const N = nums.length;

        // Starting index of the matrix chain
        const i = 1;
        
        // Ending index of the matrix chain
        const j = N - 1;

        this.dp = Array.from({ length: N }, () => Array(N).fill(-1));

        // Call the recursive function
        return this.func(nums, i, j);
    }
}

const arr = [10, 20, 30, 40, 50];

// Create an instance of Solution class
const sol = new Solution();

// Print the result
console.log(`The minimum number of operations is ${sol.matrixMultiplication(arr)}`);

Complexity Analysis:

Time Complexity: O(N*N*N), There are N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.

Space Complexity:O(N*N) + O(N). We are using an auxiliary recursion stack space O(N) and a 2D array O(N*N).

Intuition

The matrix chain multiplication problem aims to determine the optimal order of multiplying a given sequence of matrices to minimize the total number of scalar multiplications. The key insight is to utilize dynamic programming by breaking down the problem into smaller subproblems, solving each subproblem once, and storing the solutions. This method avoids redundant calculations and efficiently computes the minimum cost. The process involves considering every possible way to split the chain of matrices, calculating the cost for each split, and then choosing the split that results in the minimum cost.

Approach

Define a 2D array dp where dp[i][j] represents the minimum cost of multiplying the chain of matrices from index i to index j.
Initialize the diagonal elements of the dp array to 0, as a single matrix requires no multiplication.
Iterate over the length of the chain, starting from 2 up to the length of the matrix array.
For each length, iterate over the possible starting indices of the chain.
For each starting index, determine the ending index based on the current chain length.
For each pair of starting and ending indices, iterate over all possible split points.
Calculate the cost of multiplying the matrices at the current split point, which includes the cost of multiplying the left sub-chain, the right sub-chain, and the cost of multiplying the resulting two matrices.
Update the dp array with the minimum cost found for each pair of starting and ending indices.
The result is stored in dp[1][n-1], representing the minimum cost of multiplying the entire chain of matrices.

Solution

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

class Solution {
public:
    int matrixMultiplication(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

        // A single matrix needs no multiplication cost
        for (int i = 1; i < n; ++i) {
            dp[i][i] = 0;
        }

        // Filling the dp array
        for (int length = 2; length < n; ++length) { // length of the chain
            for (int i = 1; i <= n - length; ++i) {
                int j = i + length - 1;
                for (int k = i; k < j; ++k) {
                    int cost = dp[i][k] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        // The result is in dp[1][n-1]
        return dp[1][n - 1];
    }
};

int main() {
    Solution sol;
    vector<int> nums = {10, 15, 20, 25};
    // Output should be 8000
    cout << sol.matrixMultiplication(nums) << endl; 
    return 0;
}
class Solution {
    public int matrixMultiplication(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        // Initialize the dp array with large values
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        // A single matrix doesn't require any multiplication
        for (int i = 1; i < n; i++) {
            dp[i][i] = 0;
        }

        // Filling the dp array in a bottom-up manner
        for (int length = 2; length < n; length++) {
            for (int i = 1; i <= n - length; i++) {
                int j = i + length - 1;
                for (int k = i; k < j; k++) {
                    // Calculate cost
                    int cost = dp[i][k] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
                    // Take the minimum cost
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        // The result is in dp[1][n-1] (multiplying from matrix 1 to n-1)
        return dp[1][n - 1];
    }

    // Main method to test the solution
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {10, 15, 20, 25};
        // Output should be 8000
        System.out.println(sol.matrixMultiplication(nums)); 
    }
}
class Solution:
    def matrixMultiplication(self, nums):
        n = len(nums)
        dp = [[float('inf')] * n for _ in range(n)]

        # A single matrix needs no multiplication cost
        for i in range(1, n):
            dp[i][i] = 0

        # Filling the dp array
        for length in range(2, n):  # length of the chain
            for i in range(1, n - length + 1):
                j = i + length - 1
                for k in range(i, j):
                    cost = dp[i][k] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j]
                    if cost < dp[i][j]:
                        dp[i][j] = cost

        # The result is in dp[1][n-1]
        return dp[1][n - 1]

# Main method to test the solution
if __name__ == "__main__":
    sol = Solution()
    nums = [10, 15, 20, 25]
    print(sol.matrixMultiplication(nums))  # Output should be 8000
class Solution {
    matrixMultiplication(nums) {
        const n = nums.length;
        const dp = Array.from({ length: n }, () => Array(n).fill(Infinity));

        // A single matrix needs no multiplication cost
        for (let i = 1; i < n; i++) {
            dp[i][i] = 0;
        }

        // Filling the dp array
        for (let length = 2; length < n; length++) { // length of the chain
            for (let i = 1; i <= n - length; i++) {
                let j = i + length - 1;
                for (let k = i; k < j; k++) {
                    let cost = dp[i][k] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        // The result is in dp[1][n-1]
        return dp[1][n - 1];
    }
}

// Main method to test the solution
const sol = new Solution();
const nums = [10, 15, 20, 25];
console.log(sol.matrixMultiplication(nums)); // Output should be 8000

Complexity Analysis

Time Complexity: O(N^3) due to three nested loops

Space Complexity: O(N^2) for the dp array storage

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Identification:

Matrix Chain Multiplication:

Understanding:

Rules to solve the problem of partition DP:

To summarize:

Complexity Analysis:

Complexity Analysis:

Intuition

Approach

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code