 New update is available. Click here to update. Close
Topic list
Matrix Chain Multiplication
MEDIUM
40 mins 60 upvotes
Matrices (2D Arrays)
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Skill meter Matrices (2D Arrays)
-
- Dynamic Programming
-
-
Other topics
Problem solved
Skill meter Strings
-
- -
- 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 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

Medium 0/80
Avg time to solve 40 mins
Success Rate 60 % Share 60 upvotes

## Problem Statement

### 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 .
``````  Auto Console