Блог пользователя heavenly_phoenix

Помогите пожалуйста решить задачу на ДП.
Автор heavenly_phoenix, 10 лет назад, По-русски

Вопрос на ДП. Идей нету как решать Your text to link here...этот вопрос. Благодарен за помощь.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Давай взглянем на грамматику для ПСП.

1) S -> ''
2) S -> '(' S ')'
3) S -> S S

Из правила №1 следует, что для n = 0, k = 0 ответ 1, также если k > n ответ 0.

Из правила №2 следует, что для dp[n, k] ответ равен dp[n-1, k-1] + x.

Теперь найдём x. Для этого переберём m — место в котором мы будем разбивать текущую ПСП на две других по правилу №3. Значит x = sum(dp[m,i] * dp[n-m,j]) (Ещё надо как-то перебрать i и j, чтобы получить глубину k)

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Можно очень просто вот так: dp[n][m][k] — количество последовательностей из n скобок, сейчас открыто m, максимум было открыто k. Время куб, память при желании квадрат. Код, просто чтобы был. Набрать лучше самому, разумеется.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Можно ускорить до квадрата, если k будет иметь только два значения — требуемая вложенность уже достигнута или еще нет.

    → Ответить