DP erkennen: Überlappende Teilprobleme

Dynamische Programmierung (DP) löst komplexe Probleme, indem sie diese in einfachere, überlappende Teilprobleme zerlegt, jedes Teilproblem einmal löst und das Ergebnis speichert, um redundante Berechnungen zu vermeiden. DP ist anwendbar, wenn ein Problem zwei Eigenschaften besitzt: überlappende Teilprobleme (dasselbe Teilproblem wird bei einer naiven Rekursion mehrfach gelöst) und eine optimale Teilstruktur (die optimale Lösung lässt sich aus optimalen Lösungen für Teilprobleme aufbauen). Ohne beide Eigenschaften hilft DP nicht.

Die Fibonacci-Folge (fib(n) = fib(n-1) + fib(n-2)) ist das klassische Beispiel für überlappende Teilprobleme. Die naive Rekursion hat die exponentielle Laufzeit O(2^n), weil sie dieselben Werte wiederholt berechnet. Der Rekursionsbaum für fib(6) zeigt, dass fib(3) dreimal, fib(2) fünfmal und so weiter berechnet wird. Genau diese exponentielle Zunahme beseitigt DP, indem die berechneten Ergebnisse gespeichert werden.

Das Zeichnen des Rekursionsbaums für fib(5) macht die Verschwendung sichtbar: Jeder Knoten erzeugt zwei Kindknoten, und identische Teilbäume erscheinen wiederholt. Die Gesamtzahl der Knoten im Baum beträgt O(2^n). Wenn Sie dieses Muster sehen – identische Funktionsaufrufe mit denselben Argumenten, die im Baum wiederholt vorkommen –, deutet dies darauf hin, dass DP durch das Zwischenspeichern von Ergebnissen helfen kann. Diese Fähigkeit zur Visualisierung ist entscheidend: Wenn Sie die wiederholten Teilbäume erkennen können, wissen Sie, dass DP anwendbar ist.

Um überlappende Teilprobleme zu erkennen, schreiben Sie zunächst die Brute-Force-Rekursion und fragen Sie sich: „Gibt es mehrere rekursive Aufrufe mit DENSELBEN Argumenten?“ Wenn ja, kann DP helfen. Häufige Hinweise in Aufgabenstellungen sind Formulierungen wie „minimale/maximale Anzahl von X“, „auf wie viele Arten lässt sich Y erreichen?“ oder „kann Z erreicht werden?“. Solche Formulierungen weisen fast immer auf ein Problem mit optimaler Teilstruktur hin, bei dem die Antwort an Position i von Antworten an früheren Positionen abhängt.

Optimale Teilstruktur bedeutet, dass sich die optimale Lösung eines Problems aus optimalen Lösungen seiner Teilprobleme aufbauen lässt. Der kürzeste Pfad von A nach C über B ist beispielsweise genau dann optimal, wenn die Teilpfade A→B und B→C jeweils einzeln optimal sind. Wenn diese Eigenschaft gilt, können Sie das globale Optimum aus lokalen Optima von unten nach oben aufbauen. Probleme ohne optimale Teilstruktur (z. B. der längste Pfad in einem allgemeinen Graphen mit Zyklen) können nicht mit DP gelöst werden.

Climbing Stairs (LeetCode #70): Auf wie viele verschiedene Arten können Sie n Treppenstufen erklimmen, wenn Sie jeweils 1 oder 2 Stufen nehmen? Sei dp[i] = Anzahl der Möglichkeiten, die Stufe i zu erreichen. Sie können Stufe i von Stufe i-1 (ein Schritt) oder von Stufe i-2 (zwei Schritte) aus erreichen, daher gilt dp[i] = dp[i-1] + dp[i-2]. Das ist die Fibonacci-Folge! Basisfälle: dp[1] = 1, dp[2] = 2. Zu erkennen, dass sich „Treppensteigen“ auf Fibonacci reduzieren lässt, ist eine klassische Einsicht in Interviews.

Ein zuverlässiges dreistufiges DP-Framework: 1. Definieren Sie den Zustand — was stellt dp[i] (oder dp[i][j]) dar? Schreiben Sie dies zunächst auf Englisch auf. 2. Formulieren Sie die Rekurrenz — drücken Sie dp[i] durch kleinere Teilprobleme aus. Berücksichtigen Sie alle Fälle. 3. Bestimmen Sie die Füllreihenfolge — stellen Sie sicher, dass dp[i-1] (und andere Abhängigkeiten) vor dp[i] berechnet werden. Basisfälle initialisieren die Randbereiche. Dieses Framework verwandelt eine vage DP-Intuition in einen konkreten Implementierungsplan.

DP ist nicht immer die richtige Lösung. Verwenden Sie Greedy, wenn eine einzelne lokal optimale Entscheidung stets zur global optimalen Lösung führt (Aktivitätsauswahl, Jump Game I). Verwenden Sie Divide and Conquer, wenn sich die Teilprobleme nicht überschneiden (Merge Sort, binäre Suche). Verwenden Sie BFS, wenn es sich um die Suche nach dem kürzesten Pfad in einem ungewichteten Graphen handelt. DP ist zwar korrekt, aber oft überdimensioniert, wenn ein Greedy- oder einfacherer Ansatz existiert. Besprechen Sie in Vorstellungsgesprächen, warum Sie sich für DP und gegen die Alternativen entschieden haben.

Die Anzahl der verschiedenen Teilprobleme bestimmt die Zeit- und Speicherkomplexität von DP. Bei einer eindimensionalen DP für eine Eingabe der Größe n gibt es O(n) Teilprobleme. Bei einer zweidimensionalen DP für zwei Eingaben der Größen m und n gibt es O(mn) Teilprobleme. Wird jedes Teilproblem in O(k) Zeit gelöst (für k Auswahlmöglichkeiten in jedem Schritt), ergibt sich insgesamt O(n*k) beziehungsweise O(mn*k). Zählen Sie immer zuerst die verschiedenen Teilprobleme — damit erhalten Sie die Zeitkomplexität der DP, noch bevor Sie den Code schreiben.

House Robber (LeetCode #198) fragt nach dem maximalen Betrag, den Sie aus einer Reihe von Häusern stehlen können, ohne benachbarte Häuser auszurauben. Bei jedem Haus haben Sie die Wahl: Sie rauben es aus (addieren seinen Wert und überspringen das vorherige Haus) oder Sie überspringen es (übernehmen das beste Ergebnis des vorherigen Schritts). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Dieses Muster von Entscheidungen in jedem Schritt ist die einfachste eindimensionale DP-Rekurrenz und tritt in Dutzenden von Aufgaben aus Vorstellungsgesprächen auf.

Überprüfen Sie Ihre DP immer anhand einer Brute-Force-Lösung mit kleinen Eingaben. Brute Force dient dabei als Referenzlösung. Sobald die DP für alle Testfälle mit Brute Force übereinstimmt, wissen Sie, dass die Rekurrenz korrekt ist. Erst danach sollten Sie den Speicherbedarf optimieren. Dieser testgetriebene Ansatz — Brute Force → Top-down-DP → Bottom-up-DP → speicheroptimierte DP — ist die professionelle Methode, DP-Lösungen während eines Vorstellungsgesprächs zu entwickeln und zu überprüfen.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie gelernt: die zwei Bestandteile von DP (überlappende Teilprobleme und optimale Teilstruktur), wie Sie den Rekursionsbaum visualisieren, um wiederholte Aufrufe zu erkennen, das dreistufige DP-Framework (Zustand definieren, Rekurrenz formulieren, Füllreihenfolge festlegen) sowie erste Beispiele, darunter Fibonacci, Climbing Stairs und House Robber. Als Nächstes implementieren Sie Top-down-DP mit Memoisierung.