Самая длинная подпоследовательность S, которая сбалансирована

Заданный вопрос:



Строка скобок называется сбалансированной, если левая и правая скобки в строке могут быть правильно спарены. Например, строки(())» а также "() ()» оба сбалансированы, в то время как строка(() (» не сбалансирован.

Дана строка S длины п состоящий из скобок, предположим, что вы хотите найти самую длинную подпоследовательность S это сбалансировано. Используя динамическое программирование, спроектируйте алгоритм, который находит самую длинную сбалансированную подпоследовательность S вO (N ^ 3) время.

Мой подход:

Предположим, данная строка: S [1 2 ... n]

Допустимая подпоследовательность может заканчиваться на S [i], если S [i] == ')' то есть S [i] является закрывающей фигурной скобкой, и существует по крайней мере одна неиспользованная открывающая фигурная скобка, предшествующая S [i]. который может быть реализован в O (N).

#include
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.length(), o_count = 0, len = 0;
    for(int i=0; i 0){
            ++len;
            --o_count;
        }
    }
    cout < len < endl;
    return 0;
}
 John Kugelman25 окт. 2012 г., 19:55
@IVlad Сбалансированные скобки должны быть смежными.
 John Kugelman25 окт. 2012 г., 20:03
Ах, ты прав! Элементы в подпоследовательности неТ должен быть рядом. Я предполагаю, (г) проблема состоит в том, чтобы найти самый длинный сбалансированныйстрока поскольку самая длинная подпоследовательность является тривиальной проблемой.
 IVlad25 окт. 2012 г., 19:57
@JohnKugelman - яЯ не уверен, что вы имеете в виду.()()() является сбалансированной подпоследовательностью длины 6 (3 * 2) из()()((), Это's также самая длинная сбалансированная подпоследовательность, и OP 'Программа правильно находит (половину) своей длины.
 srbhkmr25 окт. 2012 г., 20:00
Да, возвращаемое значение - нет. пар в самой длинной подпоследовательности, которая правильно сбалансирована.
 IVlad25 окт. 2012 г., 19:52
@JohnKugelman - почему не стоитвторой будет6? Если его программа возвращает количество пар, она возвращает правильный результат для этих 2. Умножьте на 2 для фактической длины строки.
 John Kugelman25 окт. 2012 г., 19:49
Ваша программа возвращает 2 для()() и 3 для()()((), Оба должны быть 4.
 unrealsoul00727 июл. 2015 г., 15:39
@srbhkmr Почему ты согласился наO(n^3) решение, когда вышеуказанная проблема может быть решена вO(n lg n), Проверьте эту ссылку:stackoverflow.com/questions/26643697/... или в этом отношении этот вопросcodeforces.com/contest/380/problem/C

Ответы на вопрос(2)

Решение Вопроса

ЗаO(n^3) ДП это должно работать я думаю

dp[i, j] = longest balanced subsequence in [i .. j]
dp[i, i] = 0
dp[i, i + 1] = 2 if [i, i + 1] == "()", 0 otherwise

dp[i, j] = max{dp[i, k] + dp[k + 1, j] : j > i + 1} in general

Это может быть реализовано аналогично тому, какоптимальное умножение цепочки матриц является.

Ваш алгоритм мне тоже кажется правильным, посмотрите, например, на эту проблему:

http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu

Где решения в основном такие же, как у вас.

Вы игнорируете только дополнительные скобки, поэтому я нене понимаю, почему это не будетт работа.

 srbhkmr25 окт. 2012 г., 20:22
Да, я тоже считаю, что DP должен работать. Спасибо за эту ссылку, я думал, что что-то упустил с таким подходом.
 Nima22 дек. 2014 г., 18:12
Этот ответ не правильный. рассмотреть (()), алгоритм выше возвращает 0, а должно быть 4.
 Nima23 дек. 2014 г., 01:42
Вы можете найти ответ для обобщенной версии этого вопроса здесь:stackoverflow.com/questions/27583771/...
 IVlad22 дек. 2014 г., 22:31
@ Нима - этоправильно! Вы можете'примените тот же алгоритм. В этом случае ОП 'Алгоритм должен хорошо работать. К сожалению, я не могу больше удалить этот ответ.

сO(n^2) временное и пространственное решение DP в Java:

public int findLongestBalancedSubsequence(String seq, int n) {
    int[][] lengths = new int[n][n];

    for (int l = 1; l < n; l++) {
        for (int i = 0; i < n - l; i++) {
            int j = i + l;
            // Ends are balanced.
            if (seq.charAt(i) == '(' && seq.charAt(j) == ')') {
                // lengths[i, j] = max(lengths[i + 1, j - 1] + 2, lengths[i + 1, j] + 
                // lengths[i, j - 1] - lengths[i + 1, j - 1])
                if (lengths[i + 1][j - 1] + 2 > lengths[i + 1][j] +
                    lengths[i][j - 1] - lengths[i + 1][j - 1])
                    lengths[i][j] = lengths[i + 1][j - 1] + 2;
                else
                    lengths[i][j] = lengths[i + 1][j] +
                        lengths[i][j - 1] - lengths[i + 1][j - 1];
            // Ends are not balanced.
            } else {
                // lengths[i, j] = max(lengths[i + 1, j], lengths[i, j - 1])
                if (lengths[i + 1][j] > lengths[i][j - 1])
                    lengths[i][j] = lengths[i + 1][j];
                else
                    lengths[i][j] = lengths[i][j - 1];
            }
        }
    }

    return lengths[0][n - 1];
}
 William28 нояб. 2017 г., 04:24
Не могли бы вы дать некоторые объясненияlengths[i, j] = max(lengths[i + 1, j - 1] + 2, lengths[i + 1, j] + lengths[i, j - 1] - lengths[i + 1, j - 1]), Благодарю.

Ваш ответ на вопрос