90
правок
Изменения
→Решение задачи
=== Оптимизации динамическим программированием ===
Одно из простых решений — это ''мемоизация''. Каждый раз, когда мы считаем минимальную стоимость перемножения определенной подпоследовательности, давайте мы будем запоминать ответ. Если мы когда либо ещё раз захотим посчитать это ещё раз, то мы уже будет иметь ответ и не будем пересчитывать. Поскольку существует всего около <math>n^2/2</math> подотрезков, где ''n'' — это количество матриц, то память занимаемая программой будет не так велика. Можно сказать, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма (перебор) с O(<math>2^n</math>) до O(<math>n^3</math>), что является достаточно эффективным для реальных приложений.
=== Восстановление ответа ===
С помощью вышеописанного алгоритма мы можем восстановить порядок, в котором нам необходимо перемножать матрицы, чтобы достичь минимального количества арифметических операций, затрачиваемых на вычисление ответа. Когда мы узнаем, как нам нужно разбить отрезок на два подотрезка, то при восстановлении ответа мы заключаем эти два подотрезка(последовательности матриц) в скобки и передаем получившийся ответ выше по рекурсии.
=== Псевдокод ===
