House Robber : récurrence prendre ou ignorer

Le problème du voleur de maisons demande, étant donné un tableau d'entiers non négatifs représentant la somme d'argent de chaque maison, de trouver le montant maximal que vous pouvez voler sans cambrioler deux maisons adjacentes. Par exemple, [2, 7, 9, 3, 1] donne 12, en cambriolant les maisons 0, 2 et 4. Il s'agit d'un problème classique de DP 1D, dans lequel vous prenez une décision binaire à chaque étape.

Soit dp[i] le montant maximal volé dans les i+1 premières maisons. Pour chaque maison i, vous avez deux choix : la passer, en prenant dp[i-1], ou la cambrioler, en prenant nums[i] + dp[i-2]. La récurrence est dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Il s'agit du schéma fondamental prendre-ou-passer, qui apparaît dans de nombreux problèmes de DP.

Pour [2, 7, 9, 3, 1], parcourons la table : dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. La réponse finale est dp[4] = 12. Parcourir manuellement la table confirme que la récurrence gère correctement le fait de prendre ou de passer à chaque position.

La table de DP ne consulte jamais plus de deux positions en arrière, nous pouvons donc remplacer le tableau entier par deux variables : prev2, à deux étapes en arrière, et prev1, à une étape en arrière. Après chaque itération, nous les décalons : prev2 = prev1 et prev1 = current. Cela réduit la mémoire de O(n) à O(1), tout en conservant une complexité en time de O(n).

Testez toujours votre solution avec des cas limites : un tableau vide, qui doit renvoyer 0 ; un tableau à un seul élément, qui doit renvoyer cet élément ; et un tableau à deux éléments, qui doit renvoyer le maximum des deux. Lors d'un entretien, mentionner et gérer ces cas démontre votre rigueur. La condition if n == 1 évite un accès à un indice inexistant lors de l'accès à nums[1] pour dp[1].

La variante circulaire (LeetCode 213) dispose les maisons en cercle, de sorte que la première et la dernière sont adjacentes. Vous ne pouvez pas appliquer directement la récurrence linéaire. L'idée clé est la suivante : soit vous cambriolez la première maison et excluez la dernière, soit vous excluez la première et incluez la dernière. Exécutez le voleur de maisons linéaire sur les deux sous-tableaux et prenez le maximum.

Une approche gloutonne naïve pourrait essayer de toujours cambrioler la maison disponible qui a la plus grande valeur. Cependant, elle échoue avec des entrées comme [2, 1, 1, 2] : elle choisit la maison 0, d'une valeur de 2, puis la maison 3, également d'une valeur de 2, pour un total de 4, tandis que cambrioler les maisons 0 et 2 ne donne que 3. Attendez — dans ce cas, l'approche gloutonne fonctionne ! Mais essayez [1, 3, 1, 3, 100] : elle choisit les maisons de valeur 3 et 3, aux indices 1 et 3, pour un total de 6, et manque l'optimum 1+1+100 = 102. La DP est nécessaire, car des choix localement optimaux ne garantissent pas un optimum global.

Le schéma prendre-ou-passer se généralise au-delà du problème du voleur de maisons. Chaque fois que vous parcourez un tableau et qu'à chaque position vous choisissez entre inclure l'élément courant, en passant le précédent, ou l'exclure, en conservant le résultat précédent, vous avez affaire à une DP prendre-ou-passer. Repérez des contraintes comme aucun élément adjacent ou aucun intervalle qui se chevauche : elles indiquent souvent qu'il faut appliquer ce schéma.

Supprimer et gagner (LeetCode 740) demande ceci : pour chaque nombre choisi, vous gagnez num × count(num), mais devez supprimer toutes les occurrences de num-1 et num+1. Cela se réduit directement au problème du voleur de maisons : construisez un tableau earn[v] = v × count(v) pour toutes les valeurs, puis appliquez le voleur de maisons à ce tableau. Reconnaître les réductions est une compétence essentielle en entretien.

Dans Voleur de maisons III, les maisons sont disposées en arbre binaire. Vous ne pouvez pas cambrioler simultanément un nœud et son parent direct. Définissez une fonction auxiliaire qui renvoie deux valeurs : rob(node) → (rob_root, skip_root). Si vous cambriolez la racine, additionnez les valeurs correspondant au fait de ne pas cambrioler chacun de ses deux enfants. Si vous passez la racine, additionnez la meilleure valeur obtenue pour chaque enfant. Il s'agit d'un DFS en post-ordre, avec une décision prendre-ou-passer à chaque nœud.

Le voleur de maisons linéaire s'exécute en O(n) time et utilise un espace O(1) grâce à l'optimisation à deux variables. La variante circulaire s'exécute également en O(n) time, puisqu'elle appelle deux fois la version linéaire. La variante avec arbre s'exécute en O(n) time et utilise un espace O(h), où h est la hauteur de l'arbre. Lors d'un entretien, indiquez toujours la complexité après avoir écrit le code et mentionnez l'optimisation de l'espace : cela montre que vous allez au-delà d'une première solution fonctionnelle.

Évaluez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris : la récurrence prendre-ou-ignorer dp[i] = max(dp[i-1], nums[i] + dp[i-2]), la réduction de l'espace O(n) à O(1) à l'aide de deux variables mises à jour au fil du parcours, et l'extension de ce schéma aux tableaux circulaires et aux arbres binaires. Ensuite, nous étudierons les problèmes du sous-tableau de somme maximale et du sous-tableau de produit maximal à l'aide de l'algorithme de Kadane.