Изменения

[[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно <tex>n</tex>–ому [[Числа Каталана | числу Каталана]].

Например, предположим, что <tex>\dim{A }= (10 \times 30)</tex>, <tex>\dim{B } = (30 \times 5)</tex>, <tex>\dim{C } = (5 \times 60)</tex>. Тогда:

:<tex>\dim{(A}\times\dim{B})\times\dim{C} = (10\times30\times5) + (10\times5\times60) = 1500 + 3000 = 4500</tex> операций:<tex>\dim{A}\times(\dim{B}\times\dim{C}) = (30\times5\times60) + (10\times30\times60) = 9000 + 18000 = 27000</tex> операций.

В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий [[Динамическое программирование | рекурсивный алгоритм]]:

Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета <tex>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется <tex>n</tex>–ому [[Числа Каталана | числу Каталана]], да плюс вычисление для каждой правильной скобочной последовательности ''затрат'' на перемножение (то есть <tex>O(n \cdot C_n)</tex>). Так как <tex>N</tex>­-ое [[Числа Каталана | число Каталана ]] равняется <tex dpi="163"> \frac{1}{n+1}{2 n \choose n} </tex> или асимптотически <tex dpi="163"> \frac{4^n}{n^{3/2}\sqrt{\pi}} </tex>, что является а это быстро возрастающей функциейвозрастающая функциия, нам бы хотелось решение, которое работает быстрее.

<code> '''int''' dp[][] '''int''' v[] <font color="green">// dp[i][j] — ответ на отрезке [i, j)</font> '''int''' v[] <font color="green">// Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно</font> '''int''' matrixChainMultiplication('''int ''' l, '''int ''' r) <font color="green">//l — включая в отрезок //, r — исключая из отрезка. Изначально l=0, r=n, где n-длина последовательности</font> '''if''' dp[l][r] == -1 <font color="green">//Если значение динамики не посчитано</font>

dp[l][r] = 0 <font color="green"> //Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font>

dp[l][r] = infinity<tex>\infty</tex>