Problem 55305. Chain multiplication - 02
Following up on the problem in 55295, you found the number of multiplications needed to multiply two matrices.
Now, you are given a sequence of matrices. There are many different ways you can multiply the matrices. For example,
say, you are given 4 matrix - A, B, C, D. They can be multiplied as follows - A(B(CD)), A((BC)D), ((AB)C)D, (AB)(CD), (A(BC))D.
you have to figure out which is the optimal way of multiplying those matrices based on the mininum number of multiplications required. For example, consider a simple 3 matrix case.
A(1,2), B(2,3), C(3,2)
A(BC) => BC requires 12 multiplications; multiplying A matrix with the result requires 4 multiplications. Total = 12+4= 16.
(AB)C => AB requires 6 multiplications; multiplying the result with the C matrix requires 6 multiplications. Total = 6+6= 12.
Therefore, to multiply ABC - the optimal way is (AB)C requiring 12 multiplications in total.
Here, you will be given an array 'a' containing the size of consequtive matrices. The output is the minimum number of multiplications required to multiply those matrices.
here, a = [2, 4, 6, 1] represents 3 matrices -- A(2,4), B(4,6), and C(6,1)
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers11
Suggested Problems
-
Recurring Cycle Length (Inspired by Project Euler Problem 26)
118 Solvers
-
Find the sum of the elements in the "second" diagonal
1141 Solvers
-
448 Solvers
-
Return a list sorted by number of consecutive occurrences
356 Solvers
-
Determine if input is a perfect number
228 Solvers
More from this Author165
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!