Partitionierung einer Klammerkette

Ich gebe eine O (n ^ 3) -Zeit, O (n ^ 2) -Raum dynamische Programmierlösung in C ++ unten. Aber die Begründung für diesen Algorithmus erfordert zunächst eine Erklärung. Im Folgenden verwende ich "Teilzeichenfolge", um eine geordnete Teilmenge von Elementen zu bezeichnen, die zusammenhängend sein müssen, und "Teilsequenz", um eine geordnete Teilmenge zu bezeichnen, die nicht sein muss.

Generieren von Strings, von denen wir wissen, dass sie gültig sind

Definieren Sie die Tiefe einer Zeichenfolge als Anzahl von [ s, die sie enthält, minus der Anzahl von ] s.

Lassen Sie uns einige Regeln aufstellen, die alle gültigen ("ausgeglichenen") Klammerzeichenfolgen befolgen müssen:

1. Es muss eine gleiche Anzahl von [ s und ] s geben.
2. Kein Präfix der Zeichenfolge darf eine negative Tiefe haben, d. h. mehr ] s als [ s.

Dies sind einfach notwendige Bedingungen - wenn eine Zeichenkette gegen eine Regel verstößt, kann sie nicht gültig sein. Um jedoch Strings, von denen wir wissen, dass sie gültig sind, bequem generieren zu können, müssen wir zeigen, dass diese Bedingungen auch ausreichend sind : Jeder String, der diese Regeln befolgt, muss gültig sein. Um damit zu helfen, lassen Sie uns ein Lemma einführen:

Lemma: Wenn eine nicht leere Zeichenfolge den Bedingungen (1) und (2) entspricht, muss sie [] als Teilzeichenfolge enthalten.

Beweis: Es muss mit [ beginnen, da sonst das Präfix länge-1 mehr ] s als [ s enthält und (2) verletzt. Daher muss es mindestens ein ] enthalten, da sonst i & gt; = 1 [ s und 0 ] s, und eine gültige Zeichenkette muss eine gleiche Anzahl von jedem durch (1) enthalten. Daher muss ein erstes Auftreten von ] an einer Position j & gt; 1, und das Zeichen auf seiner linken Seite muss ein [ sein.

Angenommen, wir haben eine nichtleere Zeichenkette x , die den Bedingungen (1) und (2) entspricht. Nach dem Lemma muss es ein [] enthalten. Das Löschen dieses Paares kann nicht dazu führen, dass eine dieser beiden Bedingungen verletzt wird. Daher muss die resultierende Zeichenfolge, wenn sie nicht leer ist, noch die Bedingungen (1) und (2) erfüllen und muss daher irgendwo noch ein [] enthalten. Daher können wir weiterhin [] s löschen, bis uns eine leere Zeichenfolge übrig bleibt.

Das Einfügen eines [] in eine gültige Zeichenfolge an einer beliebigen Position muss eine neue gültige Zeichenfolge ergeben, da das neue Klammerpaar immer übereinstimmt und keine anderen übereinstimmenden Paare stört. Beachten Sie, dass es möglich ist, unsere ursprüngliche Zeichenkette x durch wiederholtes Einfügen von [] s in die leere Zeichenkette (was trivial gültig ist) in der umgekehrten Reihenfolge aufzubauen, wie wir sie im vorherigen Absatz gelöscht haben: Das haben wir nun bewiesen x (dh jede Zeichenkette, die den Bedingungen (1) und (2) entspricht) ist gültig.

Die richtige Rekursion

Eine äquivalente Art, die Frage des OP zu formulieren, lautet: "Wie viele Möglichkeiten können wir eine gültige Teilfolge von Zeichenpositionen auswählen, so dass die verbleibende Teilsequenz auch gültig ist?" Es ist möglich, dieses Problem mit Rekursion zu lösen, wenn wir es zuerst verallgemeinern:

Da unsere ausgewählte Subsequenz bisher die Tiefe d hat und unsere bisher nicht ausgewählte Subsequenz die Tiefe e hat, können wir eine gültige Subsequenz aus dem Suffix auswählen, die an der Position k so beginnt dass die verbleibende Teilsequenz auch gültig ist?

Rufen Sie diese Funktion count(d, e, k) auf. Die Antwort auf die ursprüngliche Frage lautet jetzt count(0, 0, 0) .

Tatsächlich können wir das Problem weiter vereinfachen, indem wir feststellen, dass d+e der Gesamttiefe nach k Zeichen entsprechen muss, sodass wir e von d und k und count() nur benötigen habe 2 Parameter.

Auch wenn getestet wird, ob es möglich ist, eine leere Teilsequenz auszuwählen, müssen wir nur d == 0 testen. Wir müssen nicht testen, ob e plus das verbleibende Suffix ohne 0 wird Wenn% ce_de% == 0 ist, dann haben wir eine Nettotiefe von 0 von der ursprünglichen Zeichenkette subtrahiert (die mit einer Tiefe von 0 enden muss und nicht unter 0 gehen darf, vorausgesetzt, dass sie gültig ist).

Um dies rekursiv zu lösen, müssen wir einen ersten Entscheidungspunkt aus dem Prozess der Suche durch alle möglichen Teilsequenzen abbrechen. Eine Teilfolge einer length-n-Zeichenfolge muss in einen der folgenden n + 1-Fälle fallen: Entweder ist sie leer oder sie hat ein Element ganz links, das eines der n Zeichen in der Zeichenfolge sein kann. Die Untersequenzen, die durch Rekursion nach dieser ersten Entscheidung erzeugt werden, sind alle verschieden.

Wenn die Rekursion richtig funktioniert, ist es einfach, sie zu notieren: einfach die richtige Antwort für jeden gegebenen Aufruf im 2D-Vektor d aufzeichnen, der anfänglich mit -1 Werten gefüllt ist. Da die Funktion memo[][] 2 Parameter hat, die von 0 bis n / 2 und von 0 bis n für eine Länge-n-Zeichenfolge reichen können, wird O (n ^ 2) -Raum benötigt, und das Innere von count(d, k) block wird höchstens O (n ^ 2) mal ausgeführt. Jedes Mal, wenn dies geschieht, wird eine O (n) -Schleife ausgeführt, die die Komplexität der Zeit bis zu O (n ^ 3) aufbringt.

Der eigentliche Code

Ergebnisse

Sie können natürlich if (memo[d][k] == -1) { oder was auch immer anstelle von long long verwenden, wenn Sie die zusätzlichen Bits benötigen.

BEARBEITEN: Fehler behoben, auf den ishi hingewiesen hat. Wenn wir die aus der ausgewählten Untersequenz auszuschließenden Zeichen überspringen, akkumuliert die Restuntersequenz sie. Was passierte, war, dass wir effektiv nur Rest-Subsequenzen ausschlossen, die bisher mehr int s als ] s auf der gesamten Subsequenz hatten - aber um eine Verletzung der Bedingung (2) zu vermeiden, müssen wir dies überprüfen true für alle Präfixe der Zeichenfolge. Wir tun dies nun, indem wir die Schleife früh stoppen, so dass diese verletzenden Rest-Teilsequenzen niemals an erster Stelle erzeugt werden. Als Bonus wird der Algorithmus schneller! :)

Wenn es eine Hilfe ist, können Sie für 'zentrische' Strings wie [[[]]] Ihre Anzahl an Möglichkeiten mit ways(1) = 2 und ways(n) = ways(n-1)*(4*n-2)/n (oder C (2n, n) wenn Sie bevorzugen), wobei n die Tiefe der Verschachtelung ist.