Группировка символов Максимальная длина Сбалансированная подпоследовательность

Question

Рассмотрим B как последовательность группировки символов (,), [,], {и}. B называется сбалансированной последовательностью, если она имеет длину 0 или B имеет одну из следующих форм: {X} Y или [X] Y или {X} Y, где X и Y сбалансированы. Пример для сбалансированного:() - {[]()} [] - ...

Теперь вопрос заключается в том, чтобы найти эффективный алгоритм для нахождения максимально сбалансированной длины подпоследовательности (не обязательно непрерывной) заданного ввода, который является строка этих символов группировки.

Например, если вход () {([)] {(])}} [], одна из подпоследовательностей макс-длина () {[] {()}} []

Я почти уверен, что это решение DP, но в любом случае я его решаю. Я нахожу примеры, в которых мой алгоритм не работает. есть только один подход, о котором я уверен, что представляет собой комбинацию DP и Divide и Conquer. Но это не эффективно, потому что так или иначе D & C часть будет решать некоторые проблемы перекрытия снова и снова.

Answer 1

Давайте сделать пару простого наблюдения:

1. Любой сбалансированный подпоследовательности можно представить в виде A1 X A2 Y, где A1 и A2 два совпадающая скобки ((), [] или {}), X и Y являются сбалансированными подпоследовательностями (они могут быть пустыми). Это верно, потому что в любой сбалансированной непустой подпоследовательности имеется крайняя левая скобка и она должна быть сопоставлена ​​чему-то.

2. X и Y являются независимыми. Если это не так, подпоследовательность не сбалансирована.

Этих наблюдения дают нам динамическое программирование решения:

Давайте предположим, что f(L, R) является самой длинной сбалансирована подпоследовательностью для [L, R] подрешетки. База представляет собой пустой подмассива. Переход следующим образом:

f(L, R) = max( 
    f(L + 1, R) // ignore the first element  
    max(f(L + 1, K - 1) + 2 + f(K + 1, R)) for all K if brackets at positions L and K match 
) 

время сложности O(N^3), потому что есть O(N^2) Подмассивов и есть O(N) переходов для каждого из них. Можно восстановить самую длинную подпоследовательность, используя стандартные методы реконструкции ответа.