Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Matrix Chain Multiplication
MEDIUM
40 mins
60 upvotes
Matrices (2D Arrays)
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Matrices (2D Arrays)
-
-
Dynamic Programming
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Matrix Chain Multiplication

Contributed by
Ishank Soni
Medium
yellow-spark
0/80
Avg time to solve 40 mins
Success Rate 60 %
Share
60 upvotes

Problem Statement

Given a chain of matrices A1, A2, A3,.....An. Your task is to find out the minimum cost to multiply these matrices. The cost of matrix multiplication is defined as the number of scalar multiplications. A Chain of matrices A1, A2, A3,.....An is represented by a sequence of numbers in an array ‘arr’ where the dimension of 1st matrix is equal to arr[0] * arr[1] , 2nd matrix is arr[1] * arr[2], and so on.

For example:

For arr[ ] = { 10, 20, 30, 40}, matrix A1 = [10 * 20], A2 = [20 * 30], A3 = [30 * 40]

Scalar multiplication of matrix with dimension 10 * 20 is equal to 200.
Detailed explanation ( Input/output format, Notes, Constraints, Images )

Sample Input 1:

2
4
4 5 3 2
4
10 15 20 25

Sample Output 1:

8000
70

Sample Output Explanation 1:

In the first test case, there are three matrices of dimensions A = [4 5], B = [5 3] and C = [3 2]. The most efficient order of multiplication is A * ( B * C).
Cost of ( B * C ) = 5 * 3 * 2 = 30  and (B * C) = [5 2] and A * (B * C) = [ 4 5] * [5 2] = 4 * 5 * 2 = 40. So the overall cost is equal to 30 + 40 =70.

In the second test case, there are two ways to multiply the chain - A1*(A2*A3) or (A1*A2)*A3.

If we multiply in order- A1*(A2*A3), then the number of multiplications required is 11250.

If we multiply in order- (A1*A2)*A3, then the number of multiplications required is 8000.

Thus a minimum number of multiplications required is 8000. 

Sample Input 2:

1
4
1 4 3 2

Sample Output 2:

18

Explanation of Sample Output 2:

In the first test case, there are three matrices of dimensions A = [1 4], B = [4 3] and C = [3 2]. The most efficient order of multiplication is (A *  B) * C .
Reset Code
Full screen
Auto
copy-code
Console