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. Retourne le montant total maximal que tu peux prendre.
Fonction
- numsinteger-array
- l’argent dans chaque maison, dans l’ordre de la rue
- Renvoieinteger
- le montant 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é de 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 consécutives, 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 donne à 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.
+16 tests cachés à la soumission
Pour aller plus loin
Retourne les maisons à prendre ainsi que le total. Que dois-tu conserver du tableau pour reconstruire cette liste, et les deux totaux cumulés peuvent-ils encore le faire ?
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 laisse à résoudre chaque choix ?
Si tu ne prends pas 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 la plus grande des deux.Remplis ces meilleurs totaux à partir du début de la rue, en commençant par 0 pour aucune maison. Chacun ne nécessite que les deux précédents, donc deux variables suffisent.
Solution
Les raccourcis évidents échouent. Prendre une maison sur deux fait manquer des plans qui sautent deux maisons d’affilée, comme 5 et 11 dans [5, 3, 4, 11, 2], et prendre d’abord la maison la plus riche échoue avec [3, 4, 3], où 4 bloque deux maisons valant ensemble 6. Ce qui fonctionne, c’est de décider 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 à chaque maison
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Regarde la dernière maison, la maison n-1. Tout plan, soit la saute, soit la prend. S’il la saute, le mieux qu’il puisse faire est de suivre le meilleur plan pour les n-1 premières maisons. S’il la prend, la maison n-2 est exclue, donc il ajoute nums[n-1] au meilleur plan pour les n-2 premières maisons. La réponse est la plus grande des deux possibilités.
Écris cela sous la forme d’une fonction most(k), qui représente le maximum que tu peux prendre parmi les k premières maisons : most(k) = max(most(k-1), most(k-2) + nums[k-1]), avec most(0) = 0 s’il n’y a aucune maison et most(1) = nums[0] s’il y en a une. Chaque plan saute ou prend sa dernière maison, donc les deux branches couvrent tous les plans et le résultat est correct.
C’est lent parce que les branches se chevauchent. most(k-1) appelle de nouveau most(k-2), donc la même question reçoit une réponse encore et encore, et le nombre d’appels augmente comme les nombres de Fibonacci, à peu près comme 1.6^n. Quarante maisons nécessitent déjà plus de 300 millions d’appels, et les tests comportent jusqu’à 10^4 maisons. Les appels s’imbriquent aussi sur n niveaux, au-delà de la limite par défaut de Python, qui est de 1000.
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 de questions que sur most(0) jusqu’à most(n) : il y a donc n + 1 questions différentes. Réponds une seule fois à chacune, stocke les réponses dans un tableau et remplis-le dans un ordre où chaque réponse que tu lis s’y trouve déjà. Quatre décisions définissent le tableau.
État : best[k] est le maximum que tu peux prendre parmi les k premières maisons. Récurrence : best[k] = max(best[k-1], best[k-2] + nums[k-1]) : ignore la maison k-1, ou prends-la en plus du meilleur résultat qui se termine avant sa voisine. Cas de base : best[0] = 0 et best[1] = nums[0]. Ordre : k de 2 jusqu’à n, car chaque entrée lit les deux entrées qui la précèdent.
Pour [5, 3, 4, 11, 2], le tableau est 0, 5, 5, 9, 16, 16. Pour k = 4, tu compares le fait d’ignorer la maison 3, qui vaut best[3] = 9, avec celui de prendre ses 11 en plus de best[2] = 5 : 16 l’emporte. La réponse est la dernière entrée. Chaque entrée nécessite une comparaison ; le temps d’exécution est donc O(n), et le tableau occupe O(n) espace.
Algorithme
- Crée un tableau
bestavec n + 1 entrées. - Définis
best[0] = 0etbest[1] = nums[0]. - Pour
kallant de 2 à n, définisbest[k]comme le plus grand debest[k-1]et debest[k-2] + nums[k-1]. - Retourne
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 du tableau ne lit que les deux entrées qui la précèdent. Une fois que best[k] est connu, best[k-2] n’est plus jamais lu. Il suffit donc de conserver deux nombres au lieu du tableau : twoBack, le meilleur total des maisons jusqu’à deux étapes en arrière, et oneBack, le meilleur total jusqu’à la maison précédente.
Pour une maison contenant x, le nouveau meilleur total est max(oneBack, twoBack + x). Ensuite, on décale : twoBack prend l’ancienne valeur de oneBack, et oneBack prend le nouveau meilleur total. Les deux commencent à 0, ce qui représente la rue vide avant la première maison ; la première maison ne nécessite donc aucun cas particulier : son meilleur total est max(0, 0 + nums[0]).
Avec [5, 3, 4, 11, 2], la paire prend les valeurs (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), et oneBack se termine à 16. Le travail est le même, O(n), qu’avec le tableau, et la mémoire passe à O(1).
Algorithme
- Définissez
twoBacketoneBackà 0. - Pour chaque montant
xdansnums, calculezcurrent = max(oneBack, twoBack + x). - Déplacez
oneBackdanstwoBack, puiscurrentdansoneBack. - Après la dernière maison, renvoyez
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
La plupart des mauvaises réponses proviennent d’un raccourci qui fonctionne avec de petites entrées, ou d’une mise à jour des deux totaux dans le mauvais ordre.
- Faire la somme des maisons paires et des maisons impaires, puis choisir la plus grande, ne tient pas compte des plans qui sautent deux maisons consécutives. Pour
[10, 1, 1, 10], les deux sommes valent 11, mais les maisons 0 et 3 rapportent 20. - Choisir d’abord la maison la plus riche échoue avec
[3, 4, 3]: on prend 4 et on bloque les deux 3, qui rapportent 6 ensemble. - Écraser
oneBackavant de le copier danstwoBackfait perdre la valeur dont la maison suivante a besoin. Calcule d’abord le nouveau maximum, puis décale les valeurs, ou attribue-les toutes les deux en même temps lorsque le langage le permet. - Lire
nums[1]ou définirbest[1]etbest[2]d’emblée échoue dans une rue qui ne compte qu’une maison. Initialiser les deux totaux à 0 évite ce cas particulier. - En Lua et en R, les tableaux commencent à 1 : l’argent de la maison
k-1se trouve donc dansnums[k].
Questions fréquentes4
Quelle est la relation de récurrence pour House Robber ?
Le meilleur total parmi les k premières maisons est max(best[k-1], best[k-2] + nums[k-1]). Tu peux soit ne pas prendre la maison k-1 et conserver le meilleur total des maisons précédentes, soit prendre la maison k-1 et l’ajouter au meilleur total qui se termine avant sa voisine. Les cas de base sont 0 pour aucune maison et nums[0] pour une maison.
Quelle est la complexité temporelle et spatiale du problème du voleur de maisons ?
La solution par programmation dynamique examine chaque maison une seule fois, elle s’exécute donc en O(n). Un tableau complet utilise un espace de O(n), tandis que le fait de ne conserver que les deux derniers totaux réduit cet espace à O(1). Une récursion simple sans mémoriser les réponses effectue environ 1.6^n appels, ce qui est exponentiel.
Pourquoi ne suffit-il pas de prendre une maison sur deux pour résoudre le problème du voleur de maisons ?
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 prendre la première et la dernière maison donne 20. La programmation dynamique compare le fait de sauter et celui de prendre chaque maison, et trouve ainsi ces plans.
Comment résoudre le problème du cambrioleur lorsque les maisons sont disposées en cercle ?
Dans un cercle, la première et la dernière maison sont voisines : un plan peut donc en prendre au maximum une des deux. Exécute la solution pour une rue droite deux fois, une fois sans la dernière maison et une fois sans la première, puis retourne le résultat le plus élevé. Une rue avec une seule maison constitue le seul 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.
Python
def rob(nums):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums = [5, 3, 4, 11, 2]
Attendu
16