House Robber I

The classic house robber problem involves selecting houses to rob such that adjacent houses cannot both be robbed, maximizing total profit.

For each house, there are two choices: rob it or skip it. The decision at each position aims to maximize accumulated wealth.

State Defniition: wealth[i] represents the maximum money obtainable from houses 0 through i.

Recurrence Relation: For house i, either skip it (wealth[i-1]) or rob it (wealth[i-2] + houses[i]). Therefore: wealth[i] = max(wealth[i-1], wealth[i-2] + houses[i])

Initialization: wealth[0] = houses[0], wealth[1] = max(houses[0], houses[1])

// Time complexity: O(n)
// Space complexity: O(n)
class RobberySolution {
public:
    int calculateMaxProfit(vector<int>& houses) {
        if (houses.empty()) return 0;
        if (houses.size() == 1) return houses[0];
        
        vector<int> wealth(houses.size(), 0);
        wealth[0] = houses[0];
        wealth[1] = max(houses[0], houses[1]);
        
        for (int i = 2; i < houses.size(); i++) {
            wealth[i] = max(wealth[i-1], wealth[i-2] + houses[i]);
        }
        
        return wealth[houses.size() - 1];
    }
};

House Robber II

This variant introduces a circular arrangement where the first and last houses are adjacent, creating an additional constraint.

The solution separates into two scenarios: excluding the first house or excluding the last house. This prevents simultaneous selection of first and last houses.

// Time complexity: O(n)
// Space complexity: O(n)
class CircularRobberySolution {
private:
    int computeRange(vector<int>& houses, int start, int end) {
        if (start == end) {
            return houses[start];
        }
        
        vector<int> profits(houses.size());
        profits[start] = houses[start];
        profits[start + 1] = max(houses[start], houses[start + 1]);
        
        for (int i = start + 2; i <= end; i++) {
            profits[i] = max(profits[i-1], profits[i-2] + houses[i]);
        }
        
        return profits[end];
    }
    
public:
    int calculateMaxProfit(vector<int>& houses) {
        if (houses.size() == 1) return houses[0];
        
        int excludeLast = computeRange(houses, 0, houses.size() - 2);
        int excludeFirst = computeRange(houses, 1, houses.size() - 1);
        
        return max(excludeLast, excludeFirst);
    }
};

House Robber III

This version transforms the problem onto a binary tree structure, where adjacent nodes (parent-child) cannot both be selected.

The approach uses post-order traversal with state tracking for each node's inclusion/exclusion decisions.

State Representation: Each node returns a pair [skip_node_profit, take_node_profit]

• Skip current node: Take maximum from left and right subtrees
• Take current node: Add current value to profits from grandchildren

// Time complexity: O(n)
// Space complexity: O(log n)
class TreeRobberySolution {
private:
    vector<int> traverse(TreeNode* node) {
        if (!node) {
            return {0, 0}; // {skip_profit, take_profit}
        }
        
        vector<int> leftResults = traverse(node->left);
        vector<int> rightResults = traverse(node->right);
        
        int skipCurrent = max(leftResults[0], leftResults[1]) + 
                         max(rightResults[0], rightResults[1]);
        int takeCurrent = node->val + leftResults[0] + rightResults[0];
        
        return {skipCurrent, takeCurrent};
    }
    
public:
    int calculateMaxProfit(TreeNode* root) {
        vector<int> result = traverse(root);
        return max(result[0], result[1]);
    }
};

Alternative approaches include memoized recursion to avoid redundant calculations in the tree variant.