House Robber
Häuser stehen in einer Reihe entlang einer Straße, 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 die größtmögliche Gesamtsumme zurück, die du nehmen kannst.
Funktion
- 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 ≤ 1040 ≤ nums[i] ≤ 1000- Die Antwort beträgt höchstens
5 × 106, also passt sie 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, um 16 zu erhalten. Zwei Häuser hintereinander zu überspringen ist erlaubt, und hier ist das besser als jeder andere Plan: 5 + 4 + 2 = 11 und 3 + 11 = 14.
- Eingabe
- nums = [3, 10, 3]
- Ausgabe
- 10
- Erklärung
- Die beiden äußeren Häuser ergeben zusammen 3 + 3 = 6. Das mittlere Haus allein ergibt 10, und wenn man es nimmt, scheiden seine beiden Nachbarn aus.
- Eingabe
- nums = [2, 9, 3, 1, 8]
- Ausgabe
- 17
- Erklärung
- 9 und 8 befinden sich in den Häusern 1 und 4, die keine Nachbarn sind, was 17 ergibt. Nimmt man vom Anfang aus jedes zweite Haus, erhält man nur 2 + 3 + 8 = 13.
Weiterführende Frage
Gib die mitzunehmenden Häuser sowie die Gesamtzahl zurück. Was musst du aus der Tabelle behalten, um diese Liste wiederherzustellen, und können zwei laufende Summen das trotzdem leisten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Betrachte das letzte Haus. Ein Plan nimmt es entweder mit oder überspringt es. Was bleibt bei jeder Wahl noch zu lösen?
Wenn du Haus
k-1auslässt, ist das Beste das Beste aus den erstenk-1Häusern. Wenn du es nimmst, addierst dunums[k-1]zum Besten aus den erstenk-2Häusern. Die Antwort fürkHäuser ist der größere der beiden Werte.Fülle diese besten Gesamtwerte vom Anfang der Straße an aus und beginne mit 0 für kein Haus. Für jeden Wert werden nur die beiden vorherigen benötigt, daher reichen zwei Variablen aus.
Lösung
Abkürzungen schlagen fehl: Jedes zweite Haus zu nehmen, lässt 5 und 11 in [5, 3, 4, 11, 2] aus, und zuerst das Haus mit dem größten Geldbetrag zu nehmen, führt bei [3, 4, 3] zu einem schlechteren Ergebnis. Entscheide stattdessen Haus für Haus: Die beste Gesamtsumme bis zu einem Haus hängt nur von den besten Gesamtsummen 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
Jeder Plan lässt entweder das letzte Haus aus oder nimmt es. Wenn du es auslässt, bleibt der beste Plan für die ersten n-1 Häuser; wenn du es nimmst, addierst du nums[n-1] zum besten Plan für die ersten n-2 Häuser. Also gilt most(k) = max(most(k-1), most(k-2) + nums[k-1]), mit most(0) = 0 und most(1) = nums[0]. Die beiden Fälle decken alle Pläne ab, daher ist die Antwort korrekt.
Die Fälle überschneiden sich: most(k-1) fragt erneut nach most(k-2), und die Anzahl der Aufrufe wächst wie die Fibonacci-Zahlen, etwa mit 1.6^n. Für vierzig Häuser sind es über 300 Millionen Aufrufe, und n erreicht 10^4.
Algorithmus
- Schreibe eine Hilfsfunktion
most(k), die zurückgibt, wie viel du höchstens aus den erstenkHäusern nehmen kannst. - Gib 0 zurück, wenn
k0 ist, undnums[0], wennk1 ist. - Berechne andernfalls
skip = most(k-1)undtake = 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): n + 1 Fragen. Beantworte jede Frage genau einmal in einer Tabelle best, beginnend mit best[0] = 0 und best[1] = nums[0], und fülle die Tabelle aufwärts ab k = 2 aus, sodass die beiden Einträge, die jede Berechnung liest, bereits vorhanden sind.
Für [5, 3, 4, 11, 2] lautet die Tabelle 0, 5, 5, 9, 16, 16. Bei k = 4 bleibt beim Überspringen von Haus 3 best[3] = 9 erhalten, während das Nehmen der 11 zusätzlich zu best[2] = 5 16 ergibt, was gewinnt. Jeder Eintrag kostet einen Vergleich: O(n) Zeit und O(n) Speicherplatz.
Algorithmus
- Erstelle eine Tabelle
bestmit n + 1 Einträgen. - Setze
best[0] = 0undbest[1] = nums[0]. - Für
kvon 2 bis n setzebest[k]auf den größeren Wert vonbest[k-1]undbest[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 liest nur die beiden Einträge davor, daher genügen zwei Zahlen statt der Tabelle: twoBack und oneBack, die besten Summen bis zu zwei Häusern zurück und bis zum vorherigen Haus. Für ein Haus mit x ist die neue beste Summe max(oneBack, twoBack + x); anschließend werden beide weitergeschoben. Beide beginnen bei 0, der leeren Straße vor dem ersten Haus, sodass eine Straße mit nur einem Haus keinen Sonderfall erfordert. Die Laufzeit bleibt O(n), und der Speicherbedarf sinkt auf O(1).
Algorithmus
- Setze
twoBackundoneBackauf 0. - Berechne für jeden Betrag
xinnumsden Wertcurrent = max(oneBack, twoBack + x). - Verschiebe
oneBacknachtwoBackund anschließendcurrentnachoneBack. - Gib nach dem letzten Haus
oneBackzurü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
oneBackzu überschreiben, bevor es intwoBackkopiert wird. Das nächste Haus liest dann die falsche Summe. Berechne zuerst den neuen Bestwert und verschiebe anschließend die Werte, oder weise beide gleichzeitig zu.nums[1]auszulesen oderbest[1]undbest[2]vorab festzulegen. Beides schlägt bei einer Straße mit nur einem Haus fehl, etwa[0].- In Lua und R beginnen Arrays bei 1, daher ist das Geld im Haus
k-1nums[k].
Häufige Fragen3
Wie hoch sind die Zeit- und die Speicherkomplexität von House Robber?
Dynamische Programmierung 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 Speicherbedarf auf O(1). Eine einfache Rekursion ohne gespeicherte Ergebnisse führt etwa 1.6^n Aufrufe aus.
Warum löst es das Problem bei „House Robber“ nicht, jedes zweite Haus auszurauben?
Der beste Plan überspringt manchmal zwei Häuser hintereinander. Bei [10, 1, 1, 10] ergeben sowohl die geraden als auch die ungeraden Häuser zusammen 11, während das erste und das letzte Haus zusammen 20 ergeben.
Wie löst man das Problem „House Robber“, wenn die Häuser einen Kreis bilden?
Bei einem Kreis sind das erste und das letzte Haus Nachbarn, daher nimmt ein Plan höchstens eines von beiden. 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. Ein einzelnes Haus ist der Sonderfall: Die Antwort ist dieses Haus.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def rob(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [5, 3, 4, 11, 2]
Erwartete Ausgabe
16