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

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «= Как считать $ValidSequencesCount$ ? = Предподсчитаем все значения этой функции динамическим прог...»)
 
 
Строка 1: Строка 1:
= Как считать $ValidSequencesCount$ ? =
+
= Задача =
 +
В получении номера по ПСП и ПСП по номеру нам потребуется вспомогательная динамика ValidSequencesCount(n, balance), где n − количество оставшихся позиций в последовательности, а balance − текущий скобочный баланс, которая возвращает количество СП такой длины и такого баланса.
 +
 
 +
= Как считать ValidSequencesCount ? =
  
 
Предподсчитаем все значения этой функции динамическим программированием.
 
Предподсчитаем все значения этой функции динамическим программированием.

Текущая версия на 15:01, 6 февраля 2021

Задача

В получении номера по ПСП и ПСП по номеру нам потребуется вспомогательная динамика ValidSequencesCount(n, balance), где n − количество оставшихся позиций в последовательности, а balance − текущий скобочный баланс, которая возвращает количество СП такой длины и такого баланса.

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