House Robber
Le case sono disposte in fila lungo una strada e nums[i] è il denaro nella casa i. Puoi prendere il denaro dalle case che vuoi, ma mai da due case adiacenti. Restituisci il totale massimo che puoi prendere.
Funzione
- numsinteger-array
- il denaro in ogni casa, nell’ordine della via
- Restituisceinteger
- il totale più grande che puoi prendere 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, è meglio di qualsiasi altro piano: 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 sceglierla esclude entrambe le case vicine.
- Input
- nums = [2, 9, 3, 1, 8]
- Output
- 17
- Spiegazione
- 9 e 8 si trovano nelle case 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.
+16 test nascosti all’invio
Per approfondire
Restituisci le case da prendere e anche il totale. Cosa devi mantenere della tabella per ricostruire quell’elenco, e i due totali progressivi possono ancora farlo?
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 delle primek-1case. Se la prendi, aggiunginums[k-1]al risultato migliore delle primek-2case. La risposta perkcase è il maggiore dei due.Compila questi totali migliori partendo dall’inizio della strada, iniziando da 0 per nessuna casa. Ciascuno richiede solo i due precedenti, quindi bastano due variabili.
Soluzione
Le scorciatoie più ovvie non funzionano. Prendere una casa sì e una no fa perdere i piani che saltano due case di fila, come 5 e 11 in [5, 3, 4, 11, 2], e prendere per prima la casa più ricca non funziona con [3, 4, 3], dove 4 esclude due case che insieme valgono 6. La soluzione è decidere 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
Guarda l'ultima casa, la casa n-1. Qualsiasi piano o la salta o la prende. Se la salta, il meglio che può fare è il miglior piano per le prime n-1 case. Se la prende, la casa n-2 è esclusa, quindi aggiunge nums[n-1] al miglior piano per le prime n-2 case. La risposta è il maggiore dei due valori.
Scrivilo come una funzione most(k), il massimo che puoi prendere dalle prime k case: most(k) = max(most(k-1), most(k-2) + nums[k-1]), con most(0) = 0 se non ci sono case e most(1) = nums[0] se ce n'è una. Ogni piano salta o prende la sua ultima casa, quindi i due casi coprono tutti i piani e il risultato è corretto.
È lento perché i casi si sovrappongono. most(k-1) richiama di nuovo most(k-2), quindi la stessa domanda riceve risposta più e più volte, e il numero di chiamate cresce come i numeri di Fibonacci, circa 1.6^n. Già quaranta case richiedono oltre 300 milioni di chiamate, e i test arrivano fino a 10^4 case. Inoltre, le chiamate si annidano per n livelli, superando il limite predefinito di Python, pari a 1000.
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 chiede solo informazioni su most(0) fino a most(n), quindi ci sono n + 1 domande diverse. Rispondi a ciascuna una sola volta, memorizzala in una tabella e riempi la tabella in un ordine tale che ogni risposta che leggi sia già disponibile. Quattro decisioni definiscono la tabella.
Stato: best[k] è il massimo che puoi ottenere dalle prime k case. Ricorrenza: best[k] = max(best[k-1], best[k-2] + nums[k-1]): salta la casa k-1, oppure prendila aggiungendola al massimo ottenibile fino alla casa prima della sua vicina. Casi base: best[0] = 0 e best[1] = nums[0]. Ordine: fai variare k da 2 fino a n, perché ogni elemento legge i due elementi precedenti.
Per [5, 3, 4, 11, 2] la tabella è 0, 5, 5, 9, 16, 16. Per k = 4 confronti il valore ottenuto saltando la casa 3, best[3] = 9, con quello ottenuto prendendo la casa con valore 11 e aggiungendolo a best[2] = 5; vince 16. La risposta è l'ultimo elemento. Ogni elemento richiede un confronto, quindi il tempo è O(n) e la tabella occupa O(n) spazio.
Algoritmo
- Crea una tabella
bestcon n + 1 voci. - Imposta
best[0] = 0ebest[1] = nums[0]. - Per
kda 2 a n, impostabest[k]al 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 voce della tabella legge solo le due voci che la precedono. Una volta noto best[k], best[k-2] non viene più letto. Quindi, invece della tabella, tieni due numeri: twoBack, il totale migliore delle case fino a due posizioni prima, e oneBack, il totale migliore fino alla casa precedente.
Per una casa che contiene x, il nuovo valore migliore è max(oneBack, twoBack + x). Poi fai lo spostamento: twoBack assume il vecchio valore di oneBack, e oneBack assume il nuovo valore migliore. Entrambi iniziano da 0, che rappresenta la strada vuota prima della prima casa, quindi la prima casa non richiede un caso speciale: il suo valore migliore è max(0, 0 + nums[0]).
Con [5, 3, 4, 11, 2] la coppia assume i valori (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), e oneBack termina con 16. Il lavoro è lo stesso O(n) della tabella, 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
La maggior parte delle risposte sbagliate deriva da una scorciatoia che funziona con input piccoli o dall’aggiornamento dei due totali nell’ordine sbagliato.
- Sommare le case pari e quelle dispari e prendere il totale più alto non considera i piani che saltano due case di fila. Con
[10, 1, 1, 10]entrambe le somme sono 11, ma le case 0 e 3 danno 20. - Scegliere per prima la casa più ricca non funziona con
[3, 4, 3]: si prende 4 e si bloccano entrambi i 3, che insieme fanno 6. - Sovrascrivere
oneBackprima di copiarlo intwoBackfa perdere il valore necessario per la casa successiva. Calcola prima il nuovo massimo, poi sposta i valori, oppure assegnali entrambi in una volta, se il linguaggio lo consente. - Leggere
nums[1]o impostarebest[1]ebest[2]all’inizio causa problemi in una strada con una sola casa. Iniziare entrambi i totali da 0 elimina il caso speciale. - In Lua e R, gli array iniziano da 1, quindi il denaro nella casa
k-1ènums[k].
Domande frequenti4
Qual è la ricorrenza per House Robber?
Il totale migliore delle prime k case è max(best[k-1], best[k-2] + nums[k-1]). Puoi saltare la casa k-1 e mantenere il risultato migliore delle case precedenti, oppure prendere la casa k-1 e aggiungerla al risultato migliore che termina prima della casa adiacente. I casi base sono 0 per nessuna casa e nums[0] per una casa.
Qual è la complessità temporale e spaziale di House Robber?
La soluzione con programmazione dinamica esamina ogni casa una sola volta, quindi richiede un tempo O(n). Una tabella completa usa O(n) spazio, mentre conservare solo gli ultimi due totali lo riduce a O(1). La ricorsione semplice senza risposte memorizzate effettua circa 1.6^n chiamate, che hanno una complessità esponenziale.
Perché prendere una casa sì e una no non risolve il problema del ladro di case?
A volte il piano migliore salta due case di fila. In [10, 1, 1, 10] le case con indice pari e quelle con indice dispari sommano entrambe 11, mentre prendere la prima e l’ultima casa dà 20. La programmazione dinamica confronta l’opzione di saltare con quella di prendere ogni casa, così trova quei piani.
Come si risolve il problema del rapinatore di case quando le case formano un cerchio?
In un cerchio, la prima e l’ultima casa sono vicine, quindi un piano può includerne al massimo una. Esegui due volte la soluzione per una strada rettilinea: una volta senza l’ultima casa e una volta senza la prima, quindi restituisci il risultato maggiore. Una strada con una sola casa è l’unico caso speciale: la risposta è quella casa.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def rob(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [5, 3, 4, 11, 2]
Atteso
16