House Robber: Rekurrenz aus Nehmen oder Überspringen

Das Problem House Robber lautet: Gegeben sei ein Array nichtnegativer Ganzzahlen, das den Geldbetrag in jedem Haus darstellt. Finden Sie den maximalen Betrag, den Sie stehlen können, ohne zwei benachbarte Häuser auszurauben. Zum Beispiel ergibt [2, 7, 9, 3, 1] den Wert 12, wenn Sie die Häuser 0, 2 und 4 ausrauben. Dies ist ein klassisches 1D-DP-Problem, bei dem Sie an jeder Position eine binäre Entscheidung treffen.

Sei dp[i] der maximale Geldbetrag, den Sie aus den ersten i+1 Häusern stehlen können. Bei jedem Haus i haben Sie zwei Möglichkeiten: es überspringen und dp[i-1] übernehmen oder es ausrauben und nums[i] + dp[i-2] übernehmen. Die Rekurrenz lautet dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Dies ist das grundlegende Take-or-Skip-Muster, das in vielen DP-Problemen vorkommt.

Für [2, 7, 9, 3, 1] können wir die Tabelle nachvollziehen: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. Die endgültige Antwort ist dp[4] = 12. Wenn Sie die Tabelle manuell nachvollziehen, können Sie überprüfen, dass die Rekurrenz an jeder Position sowohl das Auswählen als auch das Überspringen korrekt behandelt.

Die DP-Tabelle greift nur auf die zwei vorherigen Positionen zurück. Daher können wir das gesamte Array durch zwei Variablen ersetzen: prev2 für den Wert zwei Schritte zurück und prev1 für den Wert einen Schritt zurück. Nach jeder Iteration verschieben wir sie: prev2 = prev1 und prev1 = current. Dadurch reduzieren wir den Speicherbedarf von O(n) auf O(1), während die Zeitkomplexität bei O(n) bleibt.

Testen Sie Ihre Lösung immer mit Sonderfällen: einem leeren Array, für das 0 zurückgegeben wird, einem Array mit einem Element, für das dieses Element zurückgegeben wird, und einem Array mit zwei Elementen, für das das Maximum der beiden zurückgegeben wird. In Interviews zeigt das Ansprechen und Behandeln dieser Fälle, dass Sie gründlich arbeiten. Die Abfrage if n == 1 verhindert einen Indexfehler beim Zugriff auf nums[1] für dp[1].

Die kreisförmige Variante (LeetCode 213) ordnet die Häuser in einem Kreis an, sodass das erste und das letzte Haus benachbart sind. Sie können die lineare Rekurrenz nicht direkt anwenden. Die entscheidende Erkenntnis lautet: Entweder rauben Sie das erste Haus aus und schließen das letzte aus, oder Sie schließen das erste aus und nehmen das letzte auf. Führen Sie House Robber für beide Teil-Arrays aus und wählen Sie das Maximum.

Ein naiver Greedy-Ansatz könnte versuchen, immer das jeweils wertvollste verfügbare Haus auszurauben. Das scheitert jedoch bei Eingaben wie [2, 1, 1, 2]: Greedy wählt Haus 0 mit dem Wert 2 und anschließend Haus 3 mit dem Wert 2, also insgesamt 4. Das Ausrauben der Häuser 0 und 2 ergibt dagegen ebenfalls 3. Moment — in diesem Fall funktioniert Greedy! Betrachten Sie stattdessen [1, 3, 1, 3, 100]: Greedy wählt die 3 an den Indizes 1 und 3 und erhält 6, verpasst aber das Optimum 1+1+100=102. DP ist erforderlich, weil lokal optimale Entscheidungen kein globales Optimum garantieren.

Das Take-or-Skip-Muster lässt sich über House Robber hinaus verallgemeinern. Immer wenn Sie ein Array durchlaufen und an jeder Position zwischen dem Aufnehmen des aktuellen Elements — wobei das vorherige übersprungen wird — und dem Ausschließen des aktuellen Elements — wobei das bisherige Ergebnis beibehalten wird — wählen, handelt es sich um eine Take-or-Skip-DP. Achten Sie auf Einschränkungen wie keine zwei benachbarten Elemente oder keine überlappenden Intervalle; sie sind Hinweise darauf, dass dieses Muster angewendet werden kann.

Delete and Earn (LeetCode 740) fragt: Für jede ausgewählte Zahl erhalten Sie num × count(num), müssen aber alle Vorkommen von num-1 und num+1 löschen. Das lässt sich direkt auf House Robber reduzieren: Erstellen Sie für alle Werte ein Array mit earn[v] = v × count(v) und führen Sie anschließend House Robber auf diesem Array aus. Solche Reduktionen zu erkennen, ist eine wichtige Fähigkeit für Bewerbungsgespräche.

Bei House Robber III sind die Häuser als Binärbaum angeordnet. Sie können einen Knoten und seinen direkten Elternknoten nicht gleichzeitig ausrauben. Definieren Sie eine Hilfsfunktion, die zwei Werte zurückgibt: rob(node) → (rob_root, skip_root). Wenn Sie die Wurzel ausrauben, addieren Sie die Skip-Werte beider Kindknoten. Wenn Sie die Wurzel überspringen, addieren Sie für jedes Kind den jeweils besseren Wert. Dies ist eine Postorder-DFS mit einer Take-or-Skip-Entscheidung an jedem Knoten.

House Robber in der linearen Variante läuft mit der Optimierung auf zwei Variablen in O(n) Zeit und mit O(1) Speicher. Die kreisförmige Variante läuft ebenfalls in O(n) Zeit, da sie die lineare Variante zweimal aufruft. Die Baumvariante läuft in O(n) Zeit und benötigt O(h) Speicher, wobei h die Höhe des Baums ist. Geben Sie in einem Interview nach dem Programmieren immer die Komplexität an und erwähnen Sie die Speicheroptimierung — das zeigt, dass Sie über eine erste funktionierende Lösung hinausdenken.

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

In dieser Lektion haben Sie Folgendes gelernt: die Take-or-Skip-Rekurrenz dp[i] = max(dp[i-1], nums[i] + dp[i-2]), den O(n)-Speicherbedarf mithilfe von zwei rollierenden Variablen auf O(1) zu reduzieren und das Muster auf Kreisarrays und Binärbäume zu übertragen. Als Nächstes untersuchen wir die Probleme Maximum Subarray und Maximum Product Subarray mithilfe des Kadane-Algorithmus.