House Robber I - Linear Array Problem

The classic House Robber problem involves maximizing the amount of money that can be stolen from a line of houses, where adjacent houses cannot be robbed on the same night.

class Solution {
public:
    int maxLoot(vector<int>& values) {
        int houseCount = values.size();
        if (houseCount == 0) return 0;
        if (houseCount == 1) return values[0];
        
        vector<int> memo(houseCount);
        memo[0] = values[0];
        memo[1] = max(values[0], values[1]);
        
        for (int i = 2; i < houseCount; i++) {
            memo[i] = max(memo[i-1], memo[i-2] + values[i]);
        }
        
        return memo[houseCount-1];
    }
};

House Robber II - Circular Array Problem

The second variation introduces a circular arrangement of houses, meaning the first and last houses are adjaecnt. This requires considering two separate scenarios.

class Solution {
public:
    int maxLootCircular(vector<int>& values) {
        int n = values.size();
        if (n == 1) return values[0];
        
        int loot1 = calculateLoot(values, 0, n-2);  // Exclude last house
        int loot2 = calculateLoot(values, 1, n-1);  // Exclude first house
        
        return max(loot1, loot2);
    }
    
private:
    int calculateLoot(vector<int>& values, int start, int end) {
        if (start == end) return values[start];
        
        int prev2 = values[start];
        int prev1 = max(values[start], values[start + 1]);
        
        for (int i = start + 2; i <= end; i++) {
            int current = max(prev1, prev2 + values[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};

House Robber III - Binary Tree Problem

The third variation extends the problem to a binary tree structure where houses are connected as parent-child nodes, and robbing a parent prevents robbing its direct children.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 */
class Solution {
public:
    int robTree(TreeNode* root) {
        pair<int, int> result = dfs(root);  // {notRobbed, robbed}
        return max(result.first, result.second);
    }
    
private:
    pair<int, int> dfs(TreeNode* node) {
        if (!node) return {0, 0};
        
        pair<int, int> left = dfs(node->left);
        pair<int, int> right = dfs(node->right);
        
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        int rob = node->val + left.first + right.first;
        
        return {notRob, rob};
    }
};