Problem

Submissions

Solution

New

Discuss

1

Difficulty: EASY

Problem Statement

Suggest Edit

```
You don’t have to multiply the matrices, you only have to find the minimum number of multiplication operations.
```

```
ARR = {2, 4, 3, 2}
Here, we have three matrices with dimensions {2X4, 4X3, 3X2} which can be multiplied in the following ways:
a. If the order of multiplication is (2X4, 4X3)(3X2), then the total number of multiplication operations that need to be performed are: (2*4*3) + (2*3*2) = 36
b. If the order of multiplication is (2X4)(4X3, 3X2), then the total number of multiplication operations that need to be performed are (2*4*2) + (4*3*2) = 40
```

```
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains a single integer ‘N’ denoting the number of the matrices.
The second line of each test case contains ‘N + 1’ single space-separated integers denoting where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix.
```

```
For each test case, print the minimum number of multiplication operations that need to be performed to multiply all the given matrices.
Print the output of each test case on a new line.
```

```
You don’t need to print anything; It has already been taken care of.
```

```
1 <= T <= 5
1 <= N <= 100
1 <= ARR[i] <= 10^2
Time Limit: 1 sec
```

```
2
4
2 4 3 2
5
1 2 4 1 3
```

```
36
13
```

```
In the first test case, the minimum operations can be obtained by multiplying the matrices in the following order (2X4, 4X3)(3X2).
In the second test case, the minimum operations can be obtained by multiplying the matrices in the following order (1X2, (2X4, 4X1)),(1X3).
```

```
2
4
2 3 2 3
3
3 4 5
```

```
24
60
```

Console