# Matrix Chain Multiplication

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

## 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, 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