Dynamische Programmierung — Memoization und Tabulation einfach erklärt

Dynamische Programmierung ist eine Methode, Probleme zu lösen, indem man Antworten auf kleinere Teilprobleme speichert und später wiederverwendet. Sie hilft, wenn dieselben Teilprobleme mehrfach auftreten und sich die Gesamtlösung aus diesen kleineren Antworten zusammensetzen lässt.

Die zwei wichtigsten Varianten sind Memoization und Tabulation. Memoization speichert Antworten während einer rekursiven Lösung. Tabulation füllt Antworten in einer Bottom-up-Reihenfolge, meist mit einem Array oder einer Tabelle.

Wann dynamische Programmierung funktioniert

Dynamische Programmierung ist nützlich, wenn zwei Bedingungen erfüllt sind.

Erstens überlappen sich Teilprobleme. Das bedeutet, dass dasselbe Zwischenergebnis mehr als einmal gebraucht wird. Zweitens lassen sich größere Antworten auf konsistente Weise aus kleineren Antworten aufbauen.

Wenn diese Bedingungen nicht erfüllt sind, kann das Speichern alter Ergebnisse zusätzlichen Speicher kosten, ohne viel zu helfen.

Memoization vs. Tabulation

Memoization: Top-down-Speicherung

Memoization beginnt mit der rekursiven Idee. Wenn der Algorithmus ein Teilproblem zum ersten Mal löst, speichert er das Ergebnis. Spätere Aufrufe verwenden den gespeicherten Wert, statt ihn erneut zu berechnen.

Dieser Stil ist oft einfacher, wenn die Rekurrenz klar ist, aber die Reihenfolge aller benötigten Zustände nicht.

Tabulation: Bottom-up-Aufbau

Tabulation beginnt bei den Basisfällen und füllt Zustände in einer Reihenfolge, in der Abhängigkeiten verfügbar sind, wenn sie gebraucht werden.

Dieser Stil ist oft einfacher, wenn du bereits eine saubere Iterationsreihenfolge kennst und die Tabelle explizit kontrollieren möchtest.

Beispiel für dynamische Programmierung: Fibonacci

Die Fibonacci-Folge ist definiert durch

$$F(0) = 0, \quad F(1) = 1$$

und für $n \ge 2$ durch

$$F(n) = F(n-1) + F(n-2)$$

Eine einfache rekursive Lösung wiederholt Arbeit. Zum Beispiel braucht die Berechnung von $F(5)$ die Werte $F(4)$ und $F(3)$, und bei der Berechnung von $F(4)$ wird $F(3)$ noch einmal benötigt. Genau diese wiederholte Berechnung von $F(3)$ beseitigt die dynamische Programmierung.

Memoization bei Fibonacci

Mit Memoization bleibt die Rekurrenz gleich, aber jeder Wert wird gespeichert, nachdem er zum ersten Mal berechnet wurde.

Für $F(5)$ ist die nützliche Folge:

• berechne und speichere $F(0)=0$
• berechne und speichere $F(1)=1$
• berechne und speichere $F(2)=1$
• berechne und speichere $F(3)=2$
• berechne und speichere $F(4)=3$
• berechne und speichere $F(5)=5$

Der entscheidende Punkt ist, dass jeder Zustand genau einmal berechnet wird. Spätere Anfragen lesen den gespeicherten Wert.

Tabulation bei Fibonacci

Mit Tabulation baust du von den Basisfällen nach oben auf:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Diese Version macht die Abhängigkeitsreihenfolge offensichtlich: Jeder neue Wert verwendet Einträge, die bereits bekannt sind.

Warum dynamische Programmierung schneller sein kann

Wenn ein Problem nur $k$ verschiedene relevante Zustände hat, versucht die dynamische Programmierung, diese $k$ Zustände jeweils genau einmal zu lösen. Das kann einen großen Rekursionsbaum in eine viel kleinere Berechnung verwandeln.

Die genaue Beschleunigung hängt vom Problem ab. Dynamische Programmierung ist nicht automatisch schnell. Sie hilft, wenn wiederholte Arbeit ein echter Teil der ursprünglichen Lösung ist.

Häufige Fehler bei dynamischer Programmierung

Sie verwenden, obwohl sich Teilprobleme nicht überlappen

Nicht jedes rekursive Problem ist ein Problem für dynamische Programmierung. Wenn fast jedes Teilproblem anders ist, spart das Zwischenspeichern von Ergebnissen möglicherweise nicht genug Arbeit, um relevant zu sein.

Den falschen Zustand definieren

Der Zustand muss alle Informationen enthalten, die für den nächsten Schritt nötig sind. Wenn wichtige Informationen fehlen, kann die Rekurrenz gültig aussehen, aber falsche Antworten liefern.

Die Basisfälle falsch angeben

Basisfälle verankern die gesamte Methode. Wenn die Startwerte falsch sind, ist auch jeder spätere Zustand falsch, der aus ihnen aufgebaut wird.

Die Tabelle in der falschen Reihenfolge füllen

Tabulation funktioniert nur, wenn jeder Zustand erst nach den Zuständen gefüllt wird, von denen er abhängt. Eine korrekte Rekurrenz kann trotzdem scheitern, wenn die Füllreihenfolge falsch ist.

Annehmen, dass dynamische Programmierung immer Optimierung bedeutet

Viele bekannte Beispiele maximieren oder minimieren etwas, aber dynamische Programmierung wird auch für Zähl- und Entscheidungsprobleme verwendet. Das eigentliche Signal sind wiederverwendbare Teilprobleme, nicht das Wort „beste“.

Wo dynamische Programmierung eingesetzt wird

Dynamische Programmierung taucht in Problemen wie Edit Distance, längster gemeinsamer Teilfolge, dem Zählen von Pfaden, knapsack-artiger Optimierung und in einigen Kürzeste-Wege-Situationen auf.

Wenn du entscheidest, ob du sie ausprobieren solltest, stelle dir zwei Fragen:

• wiederholen sich die kleineren Teilprobleme?
• lässt sich die größere Antwort aus diesen kleineren Antworten aufbauen?

Wenn beide Antworten ja sind, ist dynamische Programmierung ein starker Kandidat.

Probiere ein ähnliches Problem aus

Probiere deine eigene Variante mit der Anzahl der Möglichkeiten, $n$ Stufen zu steigen, wenn jeder Zug entweder $1$ Stufe oder $2$ Stufen umfasst. Die Rekurrenz ist einfach, die wiederholten Teilprobleme sind leicht zu erkennen, und es ist ein gutes nächstes Beispiel nach Fibonacci.