In this tutorial, we show how to print parenthesis around matrices such that the cost of multiplication is minimized.
Matrix Chain Multiplication is a classic problem in computer science that involves finding the most optimal way of multiplying a chain of 2 dimensional matrices.
Since matrix multiplication is associative, matrixes could be multiplied simply sequentially:
A1 * A2 * A3 ...
Or, as in this example, A2 could be multiplied with A3 and then A1 could be multiplied with the result of the previous operation:
A1 * (A2 * A3) ...
In both cases the resulting matrices are identical but the costs of these operations, which is defined as the number of arithmetic operations involved in the process, may be different. So the problem is to find the best sequence of operations so as to minimize the total cost.
In this video we are going to examine two different approaches to solving this problem. The first one uses recursion with memorization to speed up the process. While the second approach employs a Dynamic Programming technique of storing partial solutions in a table and working up to the full solution. With both cases we'll be able to print the parenthesis, indicating what the cheapest sequence of multiplications.
Source code of a recursive implementation written in Java:
[ Ссылка ]
Source code of Dynamic Programming (DP) implementation written in Java:
[ Ссылка ]
Catalan Numbers:
[ Ссылка ]
Matrix Chain Multiplication defined:
[ Ссылка ]
Written and narrated by Andre Violentyev
