Количество ПСП с заданным балансом и нужной длиной: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «= Как считать $ValidSequencesCount$ ? = Предподсчитаем все значения этой функции динамическим прог...») |
Глеб (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | = Как считать | + | = Задача = |
+ | В получении номера по ПСП и ПСП по номеру нам потребуется вспомогательная динамика ValidSequencesCount(n, balance), где n − количество оставшихся позиций в последовательности, а balance − текущий скобочный баланс, которая возвращает количество СП такой длины и такого баланса. | ||
+ | |||
+ | = Как считать ValidSequencesCount ? = | ||
Предподсчитаем все значения этой функции динамическим программированием. | Предподсчитаем все значения этой функции динамическим программированием. |
Текущая версия на 15:01, 6 февраля 2021
Задача
В получении номера по ПСП и ПСП по номеру нам потребуется вспомогательная динамика ValidSequencesCount(n, balance), где n − количество оставшихся позиций в последовательности, а balance − текущий скобочный баланс, которая возвращает количество СП такой длины и такого баланса.
Как считать ValidSequencesCount ?
Предподсчитаем все значения этой функции динамическим программированием.
- База $VSC[0][0] = 1$, $VSC[0][1 \ldots n] = 0$
- Переход $VSC[n][balance] = \underbrace{VSC[n-1][balance + 1]}_{\text{ставим "("}} + \underbrace{VSC[n-1][balance - 1]}_{\text{ставим ")"}}$
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex