Ich habe verschiedene Diskussionen und Code-Versuche gesehen, das "String reduction" Problem von interviewstreet zu lösen .com, aber keiner von ihnen tut es über dynamische Programmierung.
Im Abschnitt Dynamic Programming aufgeführt, wird das Problem wie folgt beschrieben:
Wenn wir eine Zeichenfolge bestehend aus a, b und c geben, können wir die folgende Operation ausführen: Nehmen Sie zwei beliebige benachbarte Zeichen und ersetzen Sie sie durch das dritte Zeichen. Wenn beispielsweise "a" und "c" benachbart sind, können sie durch "b" ersetzt werden.
Was ist die kleinste Zeichenkette, die sich ergeben kann, wenn diese Operation wiederholt angewendet wird?
Das Problem kann mit einer erschöpfenden Brute-Force-Suche gelöst werden, wodurch effektiv ein Baum aller möglichen Substitutionen entsteht:
%Vor% Dies ist offensichtlich für größere N ( N <= 100 ) fehlgeschlagen, also versuche ich, sie in kleinere Teilprobleme zu zerlegen, sie zu memoisieren und Ergebnisse zusammenzuführen.
Das Problem ist, dass ich den Zustand nicht bestimmen kann, der "optimale Unterstruktur" hätte, um dynamische Programmierung anzuwenden ( oder mit anderen Worten, Ergebnisse von Unterproblemen "zusammenzuführen". Das Minimieren eines Teils der Zeichenfolge garantiert nicht, dass die endgültige Zeichenfolge wirklich die kleinste Lösung ist.
Was wäre in diesem Fall das Teilproblem "Staat", das mit der endgültigen Lösung zusammengeführt werden könnte?
Was das schwierig macht, ist, dass Sie dies als zwei dynamische Programmierprobleme hintereinander behandeln müssen.
i -Zeichen der Zeichenfolge reduziert werden können. (Mit der in Schritt 1 erstellten Tabelle können Sie dieses Problem rekursiv auf bereits gelöste Teilprobleme reduzieren.) Die zweite bietet Ihre Antwort. Es ist viel einfacher, wenn Sie die erste bereits gelöst haben.
Beginnen Sie mit der Erstellung einer Struktur, die eine Lösungstheorie beschreibt. Sie enthält die Anzahl der betrachteten Zeichen und die bisher codierte Zeichenkette sowie einen Worst Case und einen Best Case für die Theorie.
Am Anfang gibt es nur eine Theorie - keine Charaktere verarbeitet. Der beste Fall ist eine Zeichenfolge der Länge 1 (z. B. gilt immer eine Regel und die Zeichenfolge kann auf ein Zeichen reduziert werden, und der schlimmste Fall ist N, wo keine Regeln gelten).
%Vor%Beginnen Sie nun, den Index um eins zu erhöhen und der codierten Zeichenfolge ein Zeichen hinzuzufügen. Wenn keine Regeln gelten, bleibt diese Theorie unberührt. Wenn eine Regel zutrifft, müssen Sie eine Entscheidung treffen - entweder die Regel anwenden oder nicht. Wenn Sie also ein Zeichen hinzufügen, duplizieren Sie die Theorie für jede Regel, die für das letzte Zeichen gelten könnte, und behalten Sie eine Version für keine Regel bei. Und Sie aktualisieren den besten Fall und den schlimmsten Fall für jede Theorie.
Zunächst wird sich die Anzahl der Theorien sehr schnell vervielfachen. Aber irgendwann kommt man zu einer Situation, in der der schlechteste Fall für einige Theorien besser ist als der beste Fall für andere Theorien.
Wenn Sie also den Index weiterentwickeln, löschen Sie Theorien, bei denen der beste Fall schlechter ist als die Theorie mit dem schlechtesten Fall. Wenn sich der Index N annähert, werden die meisten Theorien ausfallen.
Spoiler-Warnungscode:
%Vor%Komplexität:
Dies ist eine O (n) -Zeitkomplexitätsoperation, da die Eingabegröße zunimmt, ist der Umfang der zu bearbeitenden Arbeit linear mit der Größe der Eingabe. Was blitzschnell ist, können wir für Megabyte große Strings verarbeiten und sie trotzdem in Bruchteilen von Sekunden verarbeiten.
Algorithmus gefunden hier mit vollständiger Analyse, warum dieser Algorithmus funktioniert:
Tags und Links algorithm dynamic-programming