Изменения

Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета <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>, а это быстро возрастающая функциия, нам бы хотелось решение, которое работает быстрее.

=== Псевдокод ===

'''int''' dp[][] <font color="green">// dp[i][j] — ответ на отрезке [i, j)</font>

'''int''' v[] <font color="green">// Массив v[] — хранит все размеры матриц по порядку

'''if''' dp[l][r] == -1 <font color="green">// Если значение динамики не посчитано</font>

'''if''' l == r - 1

*[[Задача о расстановке знаков в выражении]]

*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]

== Источники информации ==