Matrix Chain Multiplication - Dynamic Programming (DP) Print Parentheses - Java source code
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:
https://bitbucket.org/StableSort/play...
Source code of Dynamic Programming (DP) implementation written in Java:
https://bitbucket.org/StableSort/play...
Catalan Numbers:
https://en.wikipedia.org/wiki/Catalan...
Matrix Chain Multiplication defined:
https://en.wikipedia.org/wiki/Matrix_...
Written and narrated by Andre Violentyev
На этой странице сайта вы можете посмотреть видео онлайн Matrix Chain Multiplication - Dynamic Programming (DP) Print Parentheses - Java source code длительностью часов минут секунд в хорошем качестве, которое загрузил пользователь Stable Sort 04 Май 2020, поделитесь ссылкой с друзьями и знакомыми, на youtube это видео уже посмотрели 13,670 раз и оно понравилось 382 зрителям. Приятного просмотра!
