Изменения

Как бы это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнения этого алгоритма будет расти экспоненциально от <tex>n</tex> количества матриц, так как навскидку в каждую позицию мы можем поставить открывающуюся и закрывающуюся скобку, то асимптотика будет равна ''n''­-ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 числу Каталана ] или <tex>O(n * C_n)</tex>. Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и повторного использования ответа, мы сможем заметно сократить асимптотику.

Однако, если мы применим этот алгоритм, то мы обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей! Что пошло не так? Ответом на этот вопрос является то факт, что мы делаем значительное количество ненужной работы. Например, в выше описанном алгоритме, мы делали рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета ''ABC'' и ''AB''. Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется ''n''–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 числу Каталана ](то есть <tex>O(C_n)</tex>).