Простой перебор всех возможных расстановок скобок не даст эффективного алгоритма.
Разобъем матрицы на группы по три: произведение для каждой группы можно вычислить двумя способами, так что для 3 n матриц есть не менее 2n вариантов.
Шаг 1: строение оптимальной расстановки скобок
Мы должны описать строение оптимальных решений. Для задачи об умножении последовательности матриц это выглядит следующим образом. Обозначим через Ai..j матрицу, являющуюся произведением AiAi+1 … Aj . Оптимальная расстановка скобок в произведении A1A2…An разрывает последовательность между Ak и Ak+1 для некоторого k, удовлетворяющего неравенству 1£k<п. При вычислении произведения, диктуемом этой расстановкой скобок, мы сначала вычисляем произведения A1..k и Ak+1..n ) а затем перемножаем их и получаем окончательный ответ A1+n
Стоимость этой оптимальной расстановки равна стоимости вычисления матрицы A1..k плюс стоимость вычисления матрицы Ak+1..n плюс стоимость перемножения этих двух матриц.
Чем меньше умножений нам потребуется для вычисления A1..k и Ak+1..n , тем меньше будет общее число умножений.
Стало быть, оптимальное решение задачи о перемножении последовательности матриц содержит оптимальные решения задач о перемножении её частей. Это позволяет применить динамическое программирование.
Шаг 2: рекуррентное соотношение
Надо выразить стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Такими подзадачами будут задачи об оптимальной расстановке скобок в произведениях Ai..j = AiAi+1 … Aj для 1 £ i £ j £ п. Обозначим через т[i,j] минимальное количество умножений, необходимое для вычисления матрицы Ai..j
т[i,j] = 0, при i = j
Шаг 3: вычисление оптимальной стоимости
Вычисление «снизу вверх»