Давай взглянем на грамматику для ПСП.

1) S -> ''
2) S -> '(' S ')'
3) S -> S S

Из правила №1 следует, что для n = 0, k = 0 ответ 1, также если k > n ответ 0.

Из правила №2 следует, что для dp[n, k] ответ равен dp[n-1, k-1] + x.

Теперь найдём x. Для этого переберём m — место в котором мы будем разбивать текущую ПСП на две других по правилу №3. Значит x = sum(dp[m,i] * dp[n-m,j]) (Ещё надо как-то перебрать i и j, чтобы получить глубину k)

Можно очень просто вот так: dp[n][m][k] — количество последовательностей из n скобок, сейчас открыто m, максимум было открыто k. Время куб, память при желании квадрат. Код, просто чтобы был. Набрать лучше самому, разумеется.