Изменения

Будем вести подсчет с использованием метода динамического программирования. Пусть <tex dpi = 120>d[i][j]</tex> - число скобочных последовательностей длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>. Скобочную последовательность длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>, можно получить из скобочной последовательности длины <tex dpi = 120>i-1</tex> с балансом или <tex dpi = 120>j-1</tex> (добавив в конец открывающуюся скобку), или <tex dpi = 120>j+1</tex> (добавив в конец закрывающуюся скобку), т.е. <tex dpi = 120>d[i][j] = d[i-1][j-1]+d[i-1][j+1]</tex>. База <tex dpi = 120>d[0][0]</tex> = 1. Так же можно заметить, что максимальный баланс правильной скобочной последовательности длины <tex dpi = 120>2n</tex>, равен <tex dpi = 120>n</tex>. Числа <tex dpi = 120> n </tex> -ое число Каталана будут будет храниться в строке ячейке <tex dpi = 120>jd[2n][0]</tex> = 0.

'''function''' CatalanNumber(n: '''int''') d[0][0] = 1 '''for''' i = 1 '''to''' 2n '''for''' j = 0 '''to''' n d[i][j] = d[i-1][j-1] + d[i-1][j+1] '''return''' d[2n][0]