Vous incarnez un cambrioleur expérimenté qui planifie une série de vols dans des maisons situées le long d'une rue. Chaque maison recèle une certaine quantité d'argent. La seule restriction est que les systèmes de sécurité des maisons adjacentes sont interconnectés, déclenchant une alerte de police si deux maisons contiguës sont cambriolées la même nuit.

Étant donné une liste d'entiers non négatifs représentant la valeur monétaire de chaque maison, déterminez le montant maximum que vous pouvez dérober sans déclencher l'alarme.

Analyse du problème

Le scénario de cambriolage décrit se résume à trouver la somme maximale possible en sélectionnant des éléments non adjacents dans un tableau donné. Chaque élément du tableau représente le montant d'argent disponible dans une maison.

Approche par programmation dynamique

Pour résoudre ce problème, nous pouvons employer une approche de programmation dynamique. L'idée est de construire la solution de manière itérative en nous basant sur les sous-problèmes résolus.

Cas de base

• Si le tableau est vide (aucune maison à cambrioler), le montant maximal est de 0.
• Si le tableau ne contient qu'une seule maison, le montant maximal est la valeur de cette maison.

Cas général (plusieurs maisons)

Pour un tableau de n maisons, nous pouvons définir dp[i] comme le montant maximal pouvant être dérobé jusqu'à la maison i (inclusivement). La relatoin de récurrence peut être établie comme suit :

Pour décider du montant maximum à la maison i, nous avons deux options :

1. Ne pas cambrioler la maison i : Dans ce cas, le montant maximal reste le même que celui jusqu'à la maison i-1, c'est-à-dire dp[i-1].
2. Cambrioler la maison i : Si nous cambriolons la maison i, nous ne pouvons pas avoir cambriolé la maison i-1. Par conséquent, le montant maximal serait la valeur de la maison i plus le montant maximal dérobé jusqu'à la maison i-2, c'est-à-dire nums[i] + dp[i-2].

Ainsi, la formule de récurrence devient :

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

Pour gérer les cas initiaux :

• dp[0] = nums[0]
• dp[1] = max(nums[0], nums[1])

Le résultat final sera dp[n-1].

Optimisation de l'espace

En observant la formule de récurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]), on remarque que le calcul de dp[i] ne dépend que des deux valeurs précédentes (dp[i-1] et dp[i-2]). Cela nous permet d'optimiser l'utilisation de la mémoire en n'utilisant que deux variables pour conserver les motnants maximaux précédents, au lieu d'un tableau entier.

Soient prevMax le montant maximal jusqu'à la maison précédente (équivalent à dp[i-1]) et prevPrevMax le montant maximal jusqu'à l'avant-dernière maison (équivalent à dp[i-2]).

Lors de l'itération à la maison i :

• Le nouveau montant maximal actuel, currentMax, sera max(prevMax, nums[i] + prevPrevMax).
• Ensuite, nous mettons à jour prevPrevMax pour qu'il devienne l'ancien prevMax.
• Et nous mettons à jour prevMax pour qu'il devienne le currentMax calculé.

Implémentation optimisée

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }

        int prevPrevMax = nums[0]; // Montant max jusqu'à la maison 0
        int prevMax = max(nums[0], nums[1]); // Montant max jusqu'à la maison 1

        for (int i = 2; i < n; ++i) {
            // currentMax = max(ne pas robber nums[i], robber nums[i])
            int currentMax = max(prevMax, nums[i] + prevPrevMax);
            
            // Mettre à jour pour la prochaine itération
            prevPrevMax = prevMax;
            prevMax = currentMax;
        }

        return prevMax; // Le montant maximal final est le dernier prevMax calculé
    }
};
</int>

Exemple de solution alternative (approche par états)

Une autre manière de conceptualiser le problème est d'utiliser deux états pour chaque maison :

• robbed[i] : le montant maximal si la maison i est cambriolée.
• notRobbed[i] : le montant maximal si la maison i n'est pas cambriolée.

Les transitions seraient :

• notRobbed[i] = max(robbed[i-1], notRobbed[i-1]) (Si on ne cambriole pas la maison i, le montant est le maximum des états précédents).
• robbed[i] = notRobbed[i-1] + nums[i] (Si on cambriole la maison i, on ne pouvait pas avoir cambriolé la maison i-1).

On peut encore optimiser l'espace en utilisant seulement deux variables pour représenter les états précédents : maxIncludingPrev (pour robbed[i-1]) et maxExcludingPrev (pour notRobbed[i-1]).

class Solution {
public:
    int rob(vector<int> &nums) {
        int maxIncludingCurrent = 0; // Représente max(robbed[i])
        int maxExcludingCurrent = 0; // Représente max(notRobbed[i])

        for (int amount : nums) {
            // Pour calculer le nouveau maxExcludingCurrent, on prend le max entre le max précédent qui incluait et celui qui excluait.
            int tempExcluding = max(maxIncludingCurrent, maxExcludingCurrent);
            
            // Pour calculer le nouveau maxIncludingCurrent, on ajoute le montant actuel au max précédent qui excluait.
            maxIncludingCurrent = maxExcludingCurrent + amount;
            
            // Mise à jour pour la prochaine itération
            maxExcludingCurrent = tempExcluding;
        }

        // Le résultat final est le maximum entre le dernier état incluant et le dernier état excluant.
        return max(maxIncludingCurrent, maxExcludingCurrent);
    }
};
</int>