Wie kann ich mithilfe dynamischer Programmierung die maximale Summe einer Untersequenz finden?
Ich lese Skienas Algorithm Design Manual erneut, um ein paar Dinge nachzuholen, die ich seit der Schule vergessen habe, und ich bin ein wenig verblüfft von seinen Beschreibungen der Dynamischen Programmierung. Ich habe es auf Wikipedia und verschiedenen anderen Seiten nachgeschlagen, und während die Beschreibungen alle Sinn ergeben, habe ich Probleme, selbst bestimmte Probleme zu erkennen. Momentan arbeite ich an Problem 3-5 aus dem Skiena Buch. (Bei einem Array von n reellen Zahlen finden Sie die maximale Summe in jedem angrenzenden Subvektor der Eingabe.) Ich habe eine O (n ^ 2) -Lösung, wie in diese Antwort . Aber ich stecke auf der O (N) Lösung mit dynamischer Programmierung fest. Es ist mir nicht klar, wie die Wiederholungsbeziehung aussehen sollte.
Ich sehe, dass die Subsequenzen eine Menge von Summen bilden, so:
S = {a, b, c, d}
%Vor%Was ich nicht bekomme, ist, wie man wählt, welches in der linearen Zeit am größten ist. Ich habe versucht, Dinge wie die größte Summe bisher zu verfolgen, und wenn der aktuelle Wert positiv ist, fügen Sie es zur Summe hinzu. Aber wenn Sie größere Sequenzen haben, wird dies problematisch, da es möglicherweise negative Zahlenabschnitte gibt, die die Summe verringern würden, aber eine spätere große positive Zahl kann sie wieder zum Maximum machen.
Ich werde auch an summierte Bereichstabellen erinnert. Sie können alle Summen nur mit den kumulativen Summen berechnen: a, a + b, a + b + c, a + b + c + d usw. (Wenn Sie beispielsweise b + c benötigen, ist es nur (a +) b + c) - (a).) Aber sehen Sie nicht einen O (N) Weg, um es zu bekommen.
Kann mir jemand erklären, was die O (N) dynamische Programmierlösung für dieses spezielle Problem ist? Ich habe das Gefühl, dass ich es fast verstehe, aber dass mir etwas fehlt.
3 Antworten
Sie sollten sich diese pdf-Datei ansehen Schule in Ссылка hier ist es:
Die Erklärung des folgenden Pseudocodes ist auch in der pdf.
Es gibt eine Lösung, wie zum Beispiel das Array zuerst in einen Hilfsspeicher zu sortieren und dann die Longest Common Sub-Sequence-Methode auf das ursprüngliche Array und das sortierte Array anzuwenden, wobei die Summe (nicht die Länge) der gemeinsamen Subsequenz in der 2 Arrays als Eintrag in die Tabelle (Memoization). Dies kann auch das Problem lösen
Gesamtlaufzeit ist O (nlogn) + O (n ^ 2) = & gt; O (n ^ 2) Raum ist O (n) + O (n ^ 2) = & gt; O (n ^ 2)
Dies ist keine gute Lösung, wenn Speicher ins Bild kommt. Dies soll nur einen Einblick geben, wie Probleme auf einander reduziert werden können.
Bei meinem Verständnis von DP geht es darum, "einen Tisch zu machen". In der Tat bedeutet die ursprüngliche Bedeutung "Programmierung" in DP einfach Tabellen zu machen.
Der Schlüssel ist herauszufinden, was in die Tabelle oder moderne Begriffe: welcher Status zu verfolgen, oder was ist der Scheitelpunkt Schlüssel / Wert in DAG (ignorieren Sie diese Begriffe, wenn sie seltsam klingen du).
Wie wäre es, wenn dp[i] table die größte Summe ist, die am Index i des Arrays endet, zum Beispiel das Array ist [5, 15, -30, 10]
Der zweite wichtige Schlüssel ist "optimale Unterstruktur", dh "annehmen" dp[i-1] speichert bereits die größte Summe für Untersequenzen, die auf index i-1 enden, deshalb der einzige Schritt Bei i muss entschieden werden, ob a[i] in die Untersequenz eingefügt werden soll oder nicht
Der erste Begriff in max bedeutet "kein a [i]", der zweite Begriff "a [i]". Beachten Sie, wenn wir a[i] nicht einbeziehen, bleibt die bisher größte Summe dp[i-1] , was vom Argument "optimale Unterstruktur" herrührt.
Also sieht das ganze Programm so aus (in Python):
%Vor% Das Ergebnis: Die größte Summe der Untersequenz sollte das größte Element in dp table sein, nachdem i durch das Array a iteriert wurde. Aber schauen Sie sich dp genau an, es enthält alle Informationen.
Da es nur einmal Elemente im Array a durchläuft, ist es ein O (n) -Algorithmus.
Dieses Problem erscheint unsinnig, denn solange a[i] positiv ist, sollten wir es immer in die Untersequenz aufnehmen, weil es nur die Summe erhöht. Diese Intuition entspricht dem Code
Also die max. Die Summe des Untersequenzproblems ist einfach und benötigt keinerlei DP. Einfach,
%Vor%Aber was ist mit der größten Summe von "continuous sub-array" -Problemen. Alles, was wir ändern müssen, ist nur eine einzige Zeile Code
%Vor%Der erste Ausdruck besteht darin, "[i] in das kontinuierliche Unterfeld aufzunehmen", der zweite Ausdruck besteht darin, zu entscheiden, ein neues Unterfeld zu beginnen, wobei a [i] beginnt.
In diesem Fall ist dp[i] der max. summiere ein kontinuierliches Sub-Array, das mit index-i endet.
Das ist sicherlich besser als eine naive Methode O (n ^ 2) * O (n), zu for j in range(0,i): in der i-Schleife und sum zu allen möglichen Sub-Arrays.
Eine kleine Einschränkung, da die Art dp[0] gesetzt ist, wenn alle Elemente in a negativ sind, werden wir keine auswählen. Für das kontinuierliche Sub-Array mit maximaler Summe ändern wir das in
Tags und Links algorithm dynamic-programming