Вопрос Помагите!!! С задачкой по программировании

[цвыва]

Алпай очень любит математику. Особенно ему нравится возиться с выражениями, в которых много скобок. Ему попалась Олимпиадная задача, в которой надо было так расставить скобки, чтобы получилось нужное значение. Он хотел начать перебирать все варианты расстановок скобок, а потом задумался, а сколько же таких вариантов. Может для этого нужно несколько лет, а может быть и десятков и сотен лет. Помогите Алпаю узнать, сколько же имеется вариантов правильных расстановок N пар скобок

(открывающая и закрывающая скобки – одна пара).

Входные данные

Одно целое число N (1 <= N <= 35) – количество пар скобок.

Выходные данные

Единственное число – искомое количество вариантов.

Уровень сложности: 16/106 (85 %)
Пример входных данных
3
Пример выходных данных
5

 

[gsr]

это количество правильных ПСП из n открывающихся и закрывающихся скобок. Это можно посчитать динамикой d - ответ для i открывающихся и закрывающихся скобок d[0] = 1 for i in 1...n d = сумма всех d[k] * d[i - k - 1] для k = 0...i - 1

 

[читеер]

То есть: ( ) ( ) ( ) ( ) ( ( ) ) ( ( ) ) ( ) ( ( ( ) ) ) ( ( ) ( ) )