Блог пользователя feruz.atamuradov

Восстановление скобок
Автор feruz.atamuradov, история, 8 лет назад, По-русски

Помагите мне пожалуйста как решить эту задача помощью числа каталана.
Условия задача :
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Задача acmp.ru Your text to link here...

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Пусть dp[i][j] хранит количество способов так поменять знаки вопросов на префиксе длины i, что получается скобочное выражение с балансом j. Если не знаешь, что такое баланс, то поищи в гугле, там все объяснено. Тогда ответ будет храниться в dp[n][0]. Переходы такие: if (s[i] == '(') dp[i][j] = dp[i — 1][j — 1]. if (s[i] == ')') dp[i][j] = dp[i — 1][j + 1]. if (s[i] == '?') dp[i][j] = dp[i — 1][j — 1] + dp[i — 1][j + 1].

→ Ответить