Combien d'opérations de retournement de toutes les parenthèses sur une sous-chaîne d'une chaîne de parenthèses sont nécessaires pour rendre la chaîne « correcte » ?

Question

J'appelle une chaîne de parenthèses « correcte » si chaque parenthèse ouvrante a un parenthèse fermante correspondante quelque part après et si chaque parenthèse fermante a un parenthèse ouvrante correspondante quelque part avant.Par exemple

(())()((()()))

est une chaîne correcte et

)()()(

est une chaîne incorrecte.

Une opération consiste à prendre une sous-séquence contiguë de la chaîne d'entrée et à « retourner » chaque parenthèse de cette sous-séquence.

Étant donné une chaîne arbitraire de parenthèses (de longueur paire), la tâche consiste à trouver le plus petit nombre d'opérations de ce type nécessaire pour la transformer en une chaîne de parenthèses « correcte ».

Une autre façon d'aborder ce problème est d'avoir une chaîne de +1 et -1, et d'essayer de trouver le plus petit nombre d'opérations (de multiplication de chaque nombre sur un intervalle par -1) nécessaire pour rendre chaque préfixe de cette chaîne non négatif. et chaque suffixe non positif.

Answer 1

Le DP suggéré dans les commentaires de Yuval Fildus fonctionne effectivement: nous pouvons résoudre le problème dans $ \ mathcal {o} (n ^ {2}) $ par DP.

Notez d'abord que nous pouvons supposer que les intervalles ne sont pas autorisés à se chevaucher. Prenez deux intervalles de chevauchement $ [A, B) $ et $ [c, d) $ . Wlog $ a \ leq c $ . Ensuite, nous pouvons remplacer les deux intervalles avec les intervalles $ [A, c) $ et $ [\ min (b, d ), \ max (b, d)) $ qui ne se chevauchent pas, ont une longueur totale plus courte et couvrir exactement les mêmes éléments.

Remplacez les supports d'ouverture avec $ 1 $ , des crochets de fermeture avec $ - 1 $ . Maintenant, le problème correspond à l'application du nombre minimal d'opérations "intervalle multiplier par $ - 1 $ " de telle sorte que chaque préfixe a une somme non négative et la somme sur l'ensemble de la matrice est zéro.

Nous construisons une solution de gauche à droite. À chaque position, nous pouvons démarrer un intervalle ou mettre fin à un intervalle actif.

let $ DP [m] [s] [0] $ désigne le nombre minimum d'intervalles que nous devons utiliser de telle sorte que chaque somme de préfixe dans la première $ m $ éléments est non négatif, la somme de la première $ M $ éléments est $ s $ et nous n'avons pas d'intervalle actif. De même $ DP [M] [S] [1] $ est la même valeur où nous avons un intervalle actif.

si la $ m $ la valeur est $ 1 $ , pour $ 0 \ LEQ S \ LEQ M $ Nous définissons

• $ dp [m] [s] [0]= dp [m-1] [S-1] [0] $
• $ DP [m] [s] [1]= dp [m-1] [S + 1] [1] $

sinon nous définissons

• $ dp [m] [s] [0]= dp [m-1] [S + 1] [0] $
• $ dp [m] [s] [1]= dp [m-1] [S-1] [1] $ .
. .

Ensuite, nous terminons et commençons les intervalles, réglage

• $ dp [m] [s] [0]=min (dp [m] [S] [0], DP [M] [S] [1]) $
• $ dp [m] [s] [1]=min (dp [m] [S] [1], DP [M] [S] [0] + 1) $

Le boîtier de base est $ dp [0] [0] [0]= 0 $ , $ DP [0 ] [0] [1]= 1 $ .

Il y a $ \ mathcal {o} (n ^ {2}) $ états, et nous faisons $ \ Mathcal {o} (1) $ Travaillez pour calculer chacun d'eux, l'algorithme fonctionne donc dans $ \ mathcal {o} (n ^ {2}) $ . Le DP peut être mis en oeuvre pour utiliser $ \ mathcal {o} (n) $ en stockant uniquement les valeurs de $ DP $ pour la $ m $ .

Voici une implémentation C ++ de l'algorithme.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}

Answer 2

Bonne question!

Voici le problème en termes plus courants.

Parenthèses équilibrées

Une chaîne de parenthèses est équilibrée si nous pouvons la remplacer par une chaîne vide en supprimant les sous-chaînes "()" à plusieurs reprises.Par exemple, les chaînes vides, "()" et "(())()((()()))" sont équilibrées mais aucun des éléments "())" et ")()()(" n'est équilibré.

Il est clair qu'une chaîne équilibrée doit commencer par "(" et se terminer par ")".Il doit également être de longueur égale.

le problème des opérations minimales pour équilibrer une chaîne

Laisser s être une chaîne non vide de parenthèses de longueur n.La seule opération que nous pouvons effectuer est de retourner chaque parenthèse dans une sous-chaîne, c'est-à-dire de changer chaque "(" en ")" et chaque ")" en "(" pour certains caractères contigus de la chaîne.Le problème est de savoir comment trouver le plus petit nombre d'opérations qui font s équilibré.

une approche par programmation dynamique

Quels sont les sous-problèmes appropriés ?Ils sont dp[i][j] pour 0 <= i < j < n, où dp[i][j] est le nombre minimum d'opérations qui équilibrent la sous-chaîne entre l'indice i et index j compris.Le nombre minimum souhaité d'opérations qui équilibrent s est dp[0][n-1].

Étant donné qu’aucune chaîne de longueur impaire ne peut être équilibrée, nous limiterons désormais notre attention aux chaînes de longueur paire.

les cas de base dp[i][i+1] vaut 0 si la sous-chaîne entre i et i+1 est équilibré, c'est-à-dire "()".Sinon, c'est 1.

la relation de récurrenceJ'utiliserai Java pour définir la relation de récurrence.

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

La relation de récurrence provient de la propriété bien connue suivante des cordes équilibrées.Une chaîne non vide est équilibrée si et seulement si elle est la concaténation de deux chaînes équilibrées ou "(" suivi d'une chaîne équilibrée suivie de ")".

Le traitement avant le for boucle, qui définit min être dp[i + 1][j - 1] plus 0, 1 ou 2, vient du fait que "(" suivi d'une chaîne équilibrée suivie de ")" doit être une chaîne équilibrée.

Le traitement dans le for boucle, qui tente de rétrécir min à dp[i][k] + dp[k + 1][j] moins 0 ou 1 pour certains k c'est entre i et j, vient du fait que la concaténation de deux cordes équilibrées doit être une corde équilibrée.

La complexité temporelle de cette approche est $O(n^3)$.La complexité spatiale est $O(n^2)$.

Longueur des cordes "les plus déséquilibrées"

La plus petite longueur d'une chaîne qui ne peut être équilibrée par moins de 2 opérations est 4.Par exemple, ")((("

La plus petite longueur d'une chaîne qui ne peut être équilibrée par moins de 3 opérations est 10.Par exemple, ")(((((())("

La plus petite longueur d'une chaîne qui ne peut être équilibrée par moins de 4 opérations est 22.Par exemple, ")(())))(((((((((((())(".

Question:Quelle est la plus petite longueur d’une chaîne nécessitant au moins 5 opérations ?Comme je l'ai calculé, il doit être supérieur à 28.Cependant, mon calcul ne suffit pas à déterminer la valeur réelle.À quelle vitesse pouvons-nous calculer ces plus petites longueurs ?