House Robber
Le case sono disposte in fila lungo una strada e nums[i] è il denaro nella casa i. Puoi prendere il denaro da qualsiasi casa tu scelga, ma mai da due case adiacenti. Restituisci il totale più alto che puoi prendere.
Funzione
- numsinteger-array
- il denaro in ogni casa, nell’ordine della strada
- Restituisceinteger
- il totale più grande che puoi ottenere senza prendere da due case adiacenti
Vincoli
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- La risposta è al massimo
5 × 106, quindi rientra in un intero con segno a 32 bit.
Esempi
- Input
- nums = [5, 3, 4, 11, 2]
- Output
- 16
- Spiegazione
- Prendi 5 e 11 dalle case 0 e 3 per ottenere 16. È consentito saltare due case di fila e, in questo caso, è la scelta migliore: 5 + 4 + 2 = 11 e 3 + 11 = 14.
- Input
- nums = [3, 10, 3]
- Output
- 10
- Spiegazione
- Le due case alle estremità insieme danno 3 + 3 = 6. La casa centrale da sola dà 10, e prenderla esclude entrambe le case adiacenti.
- Input
- nums = [2, 9, 3, 1, 8]
- Output
- 17
- Spiegazione
- 9 e 8 si trovano nelle caselle 1 e 4, che non sono vicine, per un totale di 17. Prendendo una casa sì e una no dall’inizio, si ottiene solo 2 + 3 + 8 = 13.
Per approfondire
Restituisci le case da prendere e anche il totale. Cosa devi conservare della tabella per ricostruire quell’elenco, e possono bastare ancora due totali progressivi?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Guarda l’ultima casa. Un piano o la prende o la salta. Cosa ti resta da risolvere con ciascuna scelta?
Se salti la casa
k-1, il risultato migliore è quello ottenuto dalle primek-1case. Se la prendi, aggiunginums[k-1]al risultato migliore ottenuto dalle primek-2case. La risposta perkcase è il maggiore dei due.Compila quei totali migliori partendo dall'inizio della strada, cominciando da 0 per nessuna casa. Per ciascuno servono solo i due precedenti, quindi bastano due variabili.
Soluzione
Le scorciatoie non funzionano: prendere una casa sì e una no fa perdere 5 e 11 in [5, 3, 4, 11, 2], e prendere per prima la casa più ricca porta a un risultato peggiore con [3, 4, 3]. Decidi una casa alla volta: il totale migliore fino a una casa dipende solo dai totali migliori fino alle due case precedenti.
Prova entrambe le scelte in ogni casa
Corretto, ma non termina sui test più grandi
Intuizione
Qualsiasi piano salta l’ultima casa oppure la sceglie. Saltarla lascia il piano migliore per le prime n-1 case; sceglierla aggiunge nums[n-1] al piano migliore per le prime n-2. Quindi most(k) = max(most(k-1), most(k-2) + nums[k-1]), con most(0) = 0 e most(1) = nums[0]. I due rami coprono tutti i piani, quindi la risposta è corretta.
I rami si sovrappongono: most(k-1) richiede di nuovo most(k-2) e il numero di chiamate cresce come i numeri di Fibonacci, circa 1.6^n. Quaranta case richiedono oltre 300 milioni di chiamate e n arriva a 10^4.
Algoritmo
- Scrivi una funzione di supporto
most(k)che restituisca il massimo che puoi prendere dalle primekcase. - Restituisci 0 quando
kè 0 enums[0]quandokè 1. - Altrimenti calcola
skip = most(k-1)etake = most(k-2) + nums[k-1]. - Restituisci il maggiore dei due. La risposta è
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))Tabella bottom-up
Intuizione
La ricorsione pone domande solo su most(0) fino a most(n): n + 1 domande. Rispondi a ciascuna una sola volta in una tabella best, partendo da best[0] = 0 e best[1] = nums[0] e procedendo verso l’alto da k = 2, così che le due voci lette da ogni risposta siano già disponibili.
Per [5, 3, 4, 11, 2] la tabella è 0, 5, 5, 9, 16, 16. A k = 4, saltare la casa 3 mantiene best[3] = 9, mentre aggiungere il suo 11 a best[2] = 5 dà 16, che prevale. Ogni voce richiede un confronto: tempo O(n) e spazio O(n).
Algoritmo
- Crea una tabella
bestcon n + 1 voci. - Imposta
best[0] = 0ebest[1] = nums[0]. - Per
kda 2 a n, impostabest[k]al valore maggiore trabest[k-1]ebest[k-2] + nums[k-1]. - Restituisci
best[n].
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]Due totali progressivi
Intuizione
Ogni elemento legge solo i due elementi che lo precedono, quindi tieni due numeri invece della tabella: twoBack e oneBack, i migliori totali fino a due case prima e fino alla casa precedente. Per una casa che contiene x, il nuovo migliore è max(oneBack, twoBack + x); poi fai avanzare entrambi. Entrambi partono da 0, la strada vuota prima della prima casa, quindi una strada con una sola casa non richiede casi speciali. Il tempo rimane O(n) e la memoria scende a O(1).
Algoritmo
- Imposta
twoBackeoneBacka 0. - Per ogni importo
xinnums, calcolacurrent = max(oneBack, twoBack + x). - Sposta
oneBackintwoBack, poicurrentinoneBack. - Dopo l'ultima casa, restituisci
oneBack.
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
Trappole e casi limite
- Sovrascrivere
oneBackprima di copiarlo intwoBack. La casa successiva legge quindi il totale sbagliato. Calcola prima il nuovo massimo, poi fai lo spostamento, oppure assegna entrambi in una volta sola. - Leggere
nums[1]oppure impostare subitobest[1]ebest[2]. Entrambe le cose causano errori in una strada con una sola casa, come[0]. - In Lua e R, gli array iniziano da 1, quindi il denaro nella casa
k-1ènums[k].
Domande frequenti3
Qual è la complessità temporale e spaziale di House Robber?
La programmazione dinamica esamina ogni casa una volta, quindi richiede un tempo O(n). Una tabella completa usa O(n) spazio, mentre mantenere solo gli ultimi due totali lo riduce a O(1). La ricorsione semplice senza risposte memorizzate effettua circa 1.6^n chiamate.
Perché prendere una casa sì e una no non risolve House Robber?
A volte, il piano migliore salta due case di fila. In [10, 1, 1, 10] le case pari e quelle dispari totalizzano entrambe 11, mentre la prima e l’ultima casa danno 20.
Come si risolve il problema House Robber quando le case formano un cerchio?
In un cerchio la prima e l'ultima casa sono vicine, quindi un piano ne sceglie al massimo una. Esegui due volte la soluzione per una strada rettilinea, una volta senza l'ultima casa e una volta senza la prima, e restituisci il risultato maggiore. Una sola casa è il caso speciale: la risposta è quella casa.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def rob(nums):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
nums = [5, 3, 4, 11, 2]
Output atteso
16