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

Материал из Algocode wiki
Версия от 17:58, 6 февраля 2021; Глеб (обсуждение | вклад) (Новая страница: «= Как считать $ValidSequencesCount$ ? = Предподсчитаем все значения этой функции динамическим прог...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Как считать $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