House Robber
Des maisons sont alignées le long d’une rue, et nums[i] représente l’argent dans la maison i. Tu peux prendre l’argent dans les maisons de ton choix, mais jamais dans deux maisons côte à côte. Renvoie le montant total maximal que tu peux prendre.
Fonction
- numsinteger-array
- l'argent dans chaque maison, dans l'ordre de la rue
- Renvoieinteger
- le total le plus élevé que vous pouvez obtenir sans prendre dans deux maisons adjacentes
Contraintes
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- La réponse est au plus
5 × 106, elle tient donc dans un entier signé sur 32 bits.
Exemples
- Entrée
- nums = [5, 3, 4, 11, 2]
- Sortie
- 16
- Explication
- Prenez 5 et 11 dans les maisons 0 et 3 pour obtenir 16. Il est permis de sauter deux maisons d’affilée, et ici, cette stratégie est meilleure que toutes les autres : 5 + 4 + 2 = 11 et 3 + 11 = 14.
- Entrée
- nums = [3, 10, 3]
- Sortie
- 10
- Explication
- Les deux maisons aux extrémités donnent ensemble 3 + 3 = 6. La maison du milieu rapporte à elle seule 10, et la choisir exclut ses deux voisines.
- Entrée
- nums = [2, 9, 3, 1, 8]
- Sortie
- 17
- Explication
- 9 et 8 se trouvent dans les maisons 1 et 4, qui ne sont pas voisines, pour un total de 17. En prenant une maison sur deux à partir du début, on obtient seulement 2 + 3 + 8 = 13.
Pour aller plus loin
Renvoie les maisons à prendre ainsi que le total. Que dois-tu conserver du tableau pour reconstruire cette liste, et deux totaux cumulés peuvent-ils encore suffire ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Regarde la dernière maison. Un plan soit la prend, soit la saute. Que te reste-t-il à résoudre dans chaque cas ?
Si tu sautes la maison
k-1, le meilleur résultat est celui obtenu avec lesk-1premières maisons. Si tu la prends, tu ajoutesnums[k-1]au meilleur résultat obtenu avec lesk-2premières maisons. La réponse pourkmaisons est le plus grand des deux résultats.Remplis ces meilleurs totaux en partant du début de la rue, en commençant par 0 pour aucune maison. Chacun n’a besoin que des deux précédents, donc deux variables suffisent.
Solution
Les raccourcis échouent : prendre une maison sur deux fait manquer 5 et 11 dans [5, 3, 4, 11, 2], et prendre d’abord la maison la plus riche donne un résultat inférieur avec [3, 4, 3]. Décide maison par maison : le meilleur total jusqu’à une maison dépend uniquement des meilleurs totaux jusqu’aux deux maisons qui la précèdent.
Essaie les deux choix dans chaque maison
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Chaque plan soit ne prend pas la dernière maison, soit la prend. Ne pas la prendre laisse le meilleur plan pour les n-1 premières maisons ; la prendre ajoute nums[n-1] au meilleur plan pour les n-2 premières. Ainsi, most(k) = max(most(k-1), most(k-2) + nums[k-1]), avec most(0) = 0 et most(1) = nums[0]. Les deux branches couvrent tous les plans, donc la réponse est correcte.
Les branches se chevauchent : most(k-1) demande à nouveau most(k-2), et le nombre d’appels croît comme les nombres de Fibonacci, soit environ 1.6^n. Quarante maisons nécessitent plus de 300 millions d’appels, et n peut atteindre 10^4.
Algorithme
- Écris une fonction auxiliaire
most(k)qui renvoie le maximum que tu peux prendre parmi leskpremières maisons. - Renvoie 0 lorsque
kvaut 0, etnums[0]lorsquekvaut 1. - Sinon, calcule
skip = most(k-1)ettake = most(k-2) + nums[k-1]. - Renvoie la plus grande des deux valeurs. La réponse est
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))Tableau ascendant
Intuition
La récursion ne pose des questions que sur most(0) à most(n) : n + 1 questions. Réponds à chacune une seule fois dans un tableau best, en commençant par best[0] = 0 et best[1] = nums[0], puis en le remplissant vers le haut à partir de k = 2, de sorte que les deux entrées consultées pour chaque réponse soient déjà présentes.
Pour [5, 3, 4, 11, 2], le tableau est 0, 5, 5, 9, 16, 16. Pour k = 4, ne pas cambrioler la maison 3 conserve best[3] = 9, tandis que prendre son 11 en plus de best[2] = 5 donne 16, qui l’emporte. Chaque entrée nécessite une comparaison : temps O(n) et espace O(n).
Algorithme
- Créez un tableau
bestavec n + 1 entrées. - Définissez
best[0] = 0etbest[1] = nums[0]. - Pour
kde 2 à n, définissezbest[k]comme la plus grande valeur entrebest[k-1]etbest[k-2] + nums[k-1]. - Retournez
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]Deux totaux cumulés
Intuition
Chaque entrée ne lit que les deux entrées précédentes ; gardez donc deux nombres au lieu du tableau : twoBack et oneBack, les meilleurs totaux jusqu’à deux maisons en arrière et jusqu’à la maison précédente. Pour une maison contenant x, le nouveau meilleur total est max(oneBack, twoBack + x) ; puis faites avancer les deux valeurs. Elles commencent toutes deux à 0, pour la rue vide avant la première maison, donc une rue d’une seule maison ne nécessite aucun cas particulier. Le temps reste en O(n), et la mémoire passe à O(1).
Algorithme
- Définis
twoBacketoneBackà 0. - Pour chaque montant
xdansnums, calculecurrent = max(oneBack, twoBack + x). - Déplace
oneBackdanstwoBack, puiscurrentdansoneBack. - Après la dernière maison, retourne
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
Pièges et cas limites
- Écraser
oneBackavant de le copier danstwoBack. La maison suivante lit alors le mauvais total. Calcule d’abord le nouveau meilleur total, puis effectue le décalage, ou assigne les deux en même temps. - Lire
nums[1], ou définirbest[1]etbest[2]d’emblée. Les deux échouent dans une rue d’une seule maison, comme[0]. - En Lua et en R, les tableaux commencent à 1 : l’argent dans la maison
k-1se trouve donc dansnums[k].
Questions fréquentes3
Quelle est la complexité temporelle et spatiale de House Robber ?
La programmation dynamique examine chaque maison une seule fois, ce qui prend un temps O(n). Un tableau complet utilise un espace O(n), et ne conserver que les deux derniers totaux réduit cela à O(1). La récursion simple sans réponses mémorisées effectue environ 1.6^n appels.
Pourquoi ne suffit-il pas de cambrioler une maison sur deux pour résoudre le problème du cambrioleur ?
Le meilleur plan saute parfois deux maisons d'affilée. Dans [10, 1, 1, 10], les maisons paires et les maisons impaires totalisent toutes deux 11, tandis que la première et la dernière maison donnent 20.
Comment résoudre le problème du voleur de maisons lorsque les maisons forment un cercle ?
Dans un cercle, la première et la dernière maison sont voisines, donc un plan en prend au plus une des deux. Exécute la solution pour une rue rectiligne deux fois, une fois sans la dernière maison et une fois sans la première, puis renvoie le résultat le plus élevé. Une maison unique constitue le cas particulier : la réponse est cette maison.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def rob(nums):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
nums = [5, 3, 4, 11, 2]
Résultat attendu
16