Количество ПСП с заданным балансом и нужной длиной

Как считать $ValidSequencesCount$ ?

Предподсчитаем все значения этой функции динамическим программированием.

1. База $VSC[0][0] = 1$, $VSC[0][1 \ldots n] = 0$
2. Переход $VSC[n][balance] = \underbrace{VSC[n-1][balance + 1]}_{\text{ставим "("}} + \underbrace{VSC[n-1][balance - 1]}_{\text{ставим ")"}}$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex