198. House Robber - LeetCode

Approach: Consider two states—robbing or skipping the current house—and choose the one yielding the maximum value. Use dynamic programming with the recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        if (n == 1) {
            return nums[0];
        }
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[n-1];
    }
};

213. House Robber II - LeetCode

Approach: Since houses are arranged in a circle, consider two linear scenarios: robberies within [0, n-2] and within [1, n-1]. Take the maximum of the two outcomes.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int a = helper(nums, 0, n-2);
        int b = helper(nums, 1, n-1);
        return max(a, b);
    }
    
    int helper(vector<int>& nums, int start, int end) {
        if (start == end) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start+1] = max(nums[start], nums[start+1]);
        for (int i = start+2; i <= end; ++i) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[end];
    }
};

337. House Robber III - LeetCode

Approach: Use a tree DP approach. For each node, return a two-element array where [0] represents the maximum money when the node is not robbed, and [1] when its robbed. Recurse down the tree.

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res = traverse(root);
        return max(res[0], res[1]);
    }
    
    vector<int> traverse(TreeNode* node) {
        if (!node) return {0, 0};
        vector<int> left = traverse(node->left);
        vector<int> right = traverse(node->right);
        // Rob this node: cannot rob children
        int rob = node->val + left[0] + right[0];
        // Skip this node: take maximum from children
        int skip = max(left[0], left[1]) + max(right[0], right[1]);
        return {skip, rob};
    }
};

Summary

House robber problems rely on two states (rob or skip) and dependencies on the previous two states. For circular arrangements, split the problem into two linear cases: [0, n-2] and [1, n-1]. For tree structures, use a length‑2 array where index 0 means not robbing the node and index 1 means robbing it, then derive subsequent states from children.