ACMP 176
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Комментарии
Вид подзадачи: d[i][j] — количество последовательностей с i открывающими скобками глубиной не более j.
Рекуррентная формула: d[i][j] = ∑(d[k][j - 1] × d[i - 1 - k][j]), где k ∈ 0..(i - 1).
База рекурсии: Если i = 0, то d[i][j] = 1; если i ≠ 0 и j = 0, то d[i][j] = 0.
Вид ответа: d[n][k] - d[n][k - 1]. Сложность O(N3).