Matrix Chain Multiplication - Динамическое программирование (DP) Скобки для печати - Java

В этом уроке мы покажем, как напечатать круглые скобки вокруг матриц, чтобы минимизировать стоимость умножения.

Умножение цепочек матриц - это классическая проблема в информатике, которая включает в себя поиск наиболее оптимального способа умножения цепочки двумерных матриц.

Поскольку умножение матриц является ассоциативным, матрицы можно умножать просто последовательно:

A1 * A2 * A3 ...

Или, как в этом примере, A2 можно умножить на A3, а затем A1 можно умножить на результат предыдущей операции:

A1 * (A2 * A3) ...

В обоих случаях результирующие матрицы идентичны, но стоимость этих операций, которая определяется как число арифметических операций, вовлеченных в процесс, может быть различной. Таким образом, проблема состоит в том, чтобы найти наилучшую последовательность операций, чтобы минимизировать общую стоимость.

В этом видео мы рассмотрим два разных подхода к решению этой проблемы. Первый использует рекурсию с запоминанием, чтобы ускорить процесс. В то время как второй подход использует метод динамического программирования для хранения частичных решений в таблице и разработки до полного решения. В обоих случаях мы сможем напечатать круглые скобки с указанием самой дешевой последовательности умножений.

Исходный код рекурсивной реализации, написанной на Java:
https://bitbucket.org/StableSort/play...

Исходный код реализации динамического программирования (DP), написанный на Java:
https://bitbucket.org/StableSort/play...

Каталонские номера:
https://en.wikipedia.org/wiki/Catalan...

Определено умножение цепочки матриц:
https://en.wikipedia.org/wiki/Matrix_...