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:
- A is a 10 by 100 matrix
- B is a 100 by 5 matrix
- C is a 5 by 50 matrix
- D is a 50 by 1 matrix
- The result is an A*B*C*D 10 by 1 matrix
Within this example, there are five ways of doing this multiplication:
- (A(B(CD))) ...
