House Robber

Q: Wie lautet die Rekurrenz für House Robber?

Die beste Gesamtsumme aus den ersten k Häusern ist max(best[k-1], best[k-2] + nums[k-1]) . Entweder überspringst du Haus k-1 und behältst das Beste aus den Häusern davor bei, oder du nimmst Haus k-1 und addierst es zum besten Ergebnis, das vor seinem Nachbar endet. Die Basisfälle sind 0 für keine Häuser und nums[0] für ein Haus.

MittelDynamische Programmierung

+10

Entlang einer Straße stehen Häuser in einer Reihe, und nums[i] ist das Geld im Haus i. Du darfst das Geld aus beliebigen Häusern nehmen, aber niemals aus zwei Häusern, die nebeneinander stehen. Gib den größtmöglichen Gesamtbetrag zurück, den du nehmen kannst.

Funktion

rob(nums: integer-array) → integer

numsinteger-array: das Geld in jedem Haus, in der Reihenfolge der Straße
Gibt zurückinteger: die größte Gesamtsumme, die du mitnehmen kannst, ohne aus zwei benachbarten Häusern etwas mitzunehmen

Einschränkungen

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
Die Antwort beträgt höchstens 5 × 10⁶ und passt daher in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [5, 3, 4, 11, 2]
Ausgabe: 16
Erklärung: Nimm 5 und 11 aus den Häusern 0 und 3, das ergibt 16. Es ist erlaubt, zwei Häuser hintereinander zu überspringen, und hier ist das besser als jeder andere Plan: 5 + 4 + 2 = 11 und 3 + 11 = 14.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Gib die zu nehmenden Häuser sowie die Gesamtzahl zurück. Was musst du aus der Tabelle behalten, um diese Liste wieder aufzubauen, und können die beiden laufenden Summen das noch leisten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die naheliegenden Abkürzungen funktionieren nicht. Jedes zweite Haus zu nehmen, lässt Pläne aus, bei denen zwei Häuser hintereinander übersprungen werden, wie 5 und 11 in [5, 3, 4, 11, 2], und zuerst das wertvollste Haus zu nehmen, funktioniert bei [3, 4, 3] nicht, wo die 4 zwei Häuser blockiert, die zusammen 6 wert sind. Was funktioniert, ist, Haus für Haus zu entscheiden: Die beste Summe bis zu einem Haus hängt nur von den besten Summen bis zu den beiden Häusern davor ab.

Probiere an jedem Haus beide Möglichkeiten aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Betrachte das letzte Haus, Haus n-1. Jeder Plan lässt es entweder aus oder nimmt es. Lässt er es aus, ist das Beste, was er erreichen kann, der beste Plan für die ersten n-1 Häuser. Nimmt er es, ist Haus n-2 tabu, also addiert er nums[n-1] zum besten Plan für die ersten n-2 Häuser. Die Antwort ist der größere der beiden Werte.

Schreibe das als Funktion most(k), also den höchsten Wert, den du aus den ersten k Häusern herausholen kannst: most(k) = max(most(k-1), most(k-2) + nums[k-1]), mit most(0) = 0 für keine Häuser und most(1) = nums[0] für ein Haus. Jeder Plan lässt sein letztes Haus aus oder nimmt es, daher decken die beiden Zweige alle Pläne ab und das Ergebnis ist korrekt.

Das Verfahren ist langsam, weil sich die Zweige überschneiden. most(k-1) ruft most(k-2) erneut auf, sodass dieselbe Frage immer wieder beantwortet wird und die Anzahl der Aufrufe wie die Fibonacci-Zahlen wächst, also ungefähr wie 1.6^n. Schon 40 Häuser erfordern mehr als 300 Millionen Aufrufe, und die Tests umfassen bis zu 10^4 Häuser. Außerdem verschachteln sich die Aufrufe über n Ebenen, also über Pythons Standardlimit von 1000 hinaus.

Algorithmus

Schreibe eine Hilfsfunktion most(k), die zurückgibt, wie viel du höchstens aus den ersten k Häusern nehmen kannst.
Gib 0 zurück, wenn k 0 ist, und nums[0], wenn k 1 ist.
Berechne andernfalls skip = most(k-1) und take = most(k-2) + nums[k-1].
Gib den größeren der beiden Werte zurück. Die Antwort ist most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Bottom-up-Tabelle

Idee

Die Rekursion fragt nur nach most(0) bis most(n), also gibt es n + 1 verschiedene Fragen. Beantworte jede einmal, speichere sie in einer Tabelle und fülle die Tabelle in einer Reihenfolge, in der jede Antwort, die du abliest, bereits vorhanden ist. Vier Entscheidungen definieren die Tabelle.

Zustand: best[k] ist das Maximum, das du aus den ersten k Häusern nehmen kannst. Rekurrenz: best[k] = max(best[k-1], best[k-2] + nums[k-1]): Überspringe Haus k-1, oder nimm es zusätzlich zum besten Ergebnis, das vor seinem Nachbar endet. Basisfälle: best[0] = 0 und best[1] = nums[0]. Reihenfolge: k von 2 bis n, weil jeder Eintrag die beiden Einträge davor verwendet.

Für [5, 3, 4, 11, 2] lautet die Tabelle 0, 5, 5, 9, 16, 16. Bei k = 4 vergleichst du das Überspringen von Haus 3, das best[3] = 9 wert ist, mit dem Nehmen der 11 zusätzlich zu best[2] = 5; 16 gewinnt. Die Antwort ist der letzte Eintrag. Jeder Eintrag erfordert einen Vergleich, daher beträgt die Laufzeit O(n), und die Tabelle benötigt O(n) Speicherplatz.

Algorithmus

Erstelle eine Tabelle best mit n + 1 Einträgen.
Setze best[0] = 0 und best[1] = nums[0].
Setze für k von 2 bis n best[k] auf den größeren Wert von best[k-1] und best[k-2] + nums[k-1].
Gib best[n] zurück.

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

Zwei laufende Summen

Idee

Jeder Eintrag der Tabelle liest nur die beiden Einträge direkt davor. Sobald best[k] bekannt ist, wird best[k-2] nie wieder gelesen. Behalte also statt der Tabelle zwei Zahlen: twoBack, die beste Summe aus den Häusern bis zu dem Haus zwei Schritte zurück, und oneBack, die beste Summe bis zum vorherigen Haus.

Für ein Haus mit dem Wert x ist das neue Bestwert max(oneBack, twoBack + x). Dann verschieben: twoBack erhält den alten Wert von oneBack, und oneBack erhält den neuen Bestwert. Beide beginnen bei 0, was für die leere Straße vor dem ersten Haus steht. Daher ist für das erste Haus kein Sonderfall nötig: Sein Bestwert ist max(0, 0 + nums[0]).

Bei [5, 3, 4, 11, 2] durchläuft das Paar die Werte (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), und oneBack endet bei 16. Der Aufwand ist wie bei der Tabelle O(n), und der Speicherbedarf sinkt auf O(1).

Algorithmus

Setze twoBack und oneBack auf 0.
Berechne für jeden Betrag x in nums current = max(oneBack, twoBack + x).
Verschiebe oneBack nach twoBack und dann current nach oneBack.
Gib nach dem letzten Haus oneBack zurück.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Stolperfallen und Grenzfälle

Die meisten falschen Antworten beruhen auf einer Abkürzung, die bei kleinen Eingaben funktioniert, oder darauf, dass die beiden Summen in der falschen Reihenfolge aktualisiert werden.

Die geraden und die ungeraden Häuser zu summieren und die größere Summe zu nehmen, übersieht Pläne, bei denen zwei Häuser hintereinander ausgelassen werden. Bei [10, 1, 1, 10] sind beide Summen 11, aber die Häuser 0 und 3 ergeben 20.
Zuerst das Haus mit dem höchsten Geldbetrag zu nehmen, scheitert bei [3, 4, 3]: Du nimmst 4 und schließt beide 3er aus, die zusammen 6 ergeben.
Wenn du oneBack überschreibst, bevor du den Wert in twoBack kopierst, geht der Wert verloren, den das nächste Haus benötigt. Berechne zuerst den neuen Bestwert und verschiebe dann die Werte, oder weise beide gleichzeitig zu, wenn die Sprache das erlaubt.
nums[1] auszulesen oder best[1] und best[2] gleich am Anfang festzulegen, führt bei einer Straße mit nur einem Haus zu Fehlern. Wenn du beide Summen bei 0 beginnen lässt, entfällt der Sonderfall.
In Lua und R beginnen Arrays bei 1, daher ist das Geld im Haus k-1 nums[k].

Häufige Fragen4

Wie lautet die Rekurrenz für House Robber?

Die beste Gesamtsumme aus den ersten k Häusern ist max(best[k-1], best[k-2] + nums[k-1]). Entweder überspringst du Haus k-1 und behältst das Beste aus den Häusern davor bei, oder du nimmst Haus k-1 und addierst es zum besten Ergebnis, das vor seinem Nachbar endet. Die Basisfälle sind 0 für keine Häuser und nums[0] für ein Haus.

Wie hoch sind die Zeit- und die Speicherkomplexität von House Robber?

Die dynamische Programmierlösung betrachtet jedes Haus genau einmal und benötigt daher O(n) Zeit. Eine vollständige Tabelle benötigt O(n) Speicherplatz, und wenn nur die letzten beiden Summen gespeichert werden, sinkt der Speicherplatzbedarf auf O(1). Eine einfache Rekursion ohne gespeicherte Ergebnisse führt etwa 1.6^n Aufrufe aus, was exponentiell ist.

Warum löst man das Problem „House Robber“ nicht, indem man jedes zweite Haus ausraubt?

Der beste Plan überspringt manchmal zwei Häuser hintereinander. Bei [10, 1, 1, 10] ergeben sowohl die geradzahligen als auch die ungeradzahligen Häuser zusammen 11, während die Wahl des ersten und des letzten Hauses 20 ergibt. Dynamische Programmierung vergleicht bei jedem Haus das Überspringen und das Nehmen und findet so diese Pläne.

Wie löst man das Problem „House Robber“, wenn die Häuser im Kreis angeordnet sind?

In einem Kreis sind das erste und das letzte Haus Nachbarn, daher kann ein Plan höchstens eines von ihnen umfassen. Führe die Lösung für eine gerade Straße zweimal aus: einmal ohne das letzte Haus und einmal ohne das erste, und gib das größere Ergebnis zurück. Eine Straße mit nur einem Haus ist der Sonderfall: Die Antwort ist dieses Haus.

Python

def rob(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [5, 3, 4, 11, 2]

Erwartet

House Robber

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere an jedem Haus beide Möglichkeiten aus

Bottom-up-Tabelle

Zwei laufende Summen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben