April 2018
Beginner to intermediate
426 pages
10h 19m
English
Matrix chain multiplication is another famous problem that can be solved with dynamic programming. The problem consists of finding the best way (order) of multiplying a set of matrices.
Let's try to understand the problem a little better. To multiply two matrices, A being a matrix m by n, and B a matrix m by p. The result is matrix C, n by p.
Now, consider that we want to multiply A*B*C*D. As multiplication is associative, we can multiply these matrices in any order. So, let's consider the following:
Within this example, there are five ways of doing this multiplication: