Optimal Matrix Multiplication#9647
Given two matrices A and B, we can determine the matrix C = AB using the standard definition of matrix multiplication:
The number of columns in the matrix A must be the same as the number of rows in the matrix B. Let matrix A have size m × n, matrix B has size n × p. Then matrix С will have the size m × p, and to calculate it you should perform m * n * p multiplications.
For example, if size of A is 10 × 20, size of B is 20 × 15, it will take 10 × 20 × 15 = 3000 multiplications to compute matrix C.
Multiplication of more than two matrices can be done in multiple ways. For example, if X, Y and Z are matrices, then XYZ computation can be done either like (XY)Z or X(YZ). Let size of X be 5 × 10, size of Y be 10 × 20, and size of Z be 20 × 35.
Let's look at the number of multiplications required to compute the product using two different ways:
(XY)Z
5 × 20 × 10 = 1000 multiplications to determine the product (XY) that has size 5 × 20.
Then 5 × 35 × 20 = 3500 multiplications to determine the final result.
Total number of multiplications: 4500.
X(YZ)
10 × 35 × 20 = 7000 multiplications to determine the product (YZ) that has size 10 × 35.
Then 5 × 35 × 10 multiplications to determine the final result.
Total number of multiplications: 8750.
Clearly we'll be able to compute (XY)Z using fewer individual multiplications.
Given the sequence of matrices to be multiplied, you are to determine the optimal order of their multiplication. Optimality in this problem is relative to the number of scalar multiplications required.
First line contains the number n (n ≤ 10) of matrices to be multiplied. It is followed by n pairs of integers, each pair giving the number of rows and columns in a matrix, matrix sizes are given in the order of their multiplication.
Print the minimum number of multiplications sufficient to multiply all matrices.
Example 1
Example 2