House Robber I, II, II

XXX. House Robber Problems

Dynamic Programming

Recursion

Tree

Problem Statement:

Solve the "House Robber" problems:

1. House Robber I: Rob houses along a street such that no two adjacent houses are robbed.
2. House Robber II: Rob houses arranged in a circle such that no two adjacent houses are robbed.
3. House Robber III: Rob houses arranged in a binary tree such that no two directly connected houses are robbed.

Algorithm:

1. House Robber I:
   • Use dynamic programming to track the maximum amount of money that can be robbed up to each house.
   • Maintain two variables for the maximum sums including and excluding the current house.
2. House Robber II:
   • Handle the circular arrangement by solving two subproblems: excluding the first house or excluding the last house.
   • Use the same DP approach as House Robber I for both subproblems.
3. House Robber III:
   • Use a DFS approach to traverse the binary tree.
   • At each node, calculate the maximum money by either robbing the current node or not robbing it.
   • Store results in a map to avoid recomputation.

Complexity:

House Robber I: O(n) time, O(1) space.
House Robber II: O(n) time, O(1) space.
House Robber III: O(n) time, O(h) space, where h is the height of the tree.

Java Implementation:

// House Robber I
public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int twoBefore = nums[0];
    int oneBefore = Math.max(nums[0], nums[1]);
    int max = oneBefore;

    for (int i = 2; i < nums.length; i++) {
        int currHouse = nums[i];
        max = Math.max(currHouse + twoBefore, oneBefore);
        twoBefore = oneBefore;
        oneBefore = max;
    }

    return max;
}

// House Robber II
public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

    private int rob(int[] nums, int start, int end) {
        if (end < start) return 0;

        int twoBefore = nums[start];
        int oneBefore = Math.max(nums[start], nums[start + 1]);
        int max = oneBefore;

        for (int i = start + 2; i <= end; i++) {
            int currHouse = nums[i];
            max = Math.max(currHouse + twoBefore, oneBefore);
            twoBefore = oneBefore;
            oneBefore = max;
        }

        return max;
    }
}

// House Robber III
public int rob(TreeNode root) {
    Map dp = new HashMap<>();
    return dfs(root, dp);
}

public int dfs(TreeNode node, Map map) {
    if (node == null) return 0;
    if (map.containsKey(node)) return map.get(node);

    int rob = node.val;
    if (node.left != null)
        rob += dfs(node.left.left, map) + dfs(node.left.right, map);
    if (node.right != null)
        rob += dfs(node.right.left, map) + dfs(node.right.right, map);

    int dontRob = dfs(node.right, map) + dfs(node.left, map);
    int res = Math.max(rob, dontRob);
    map.put(node, res);

    return res;
}
                

Python Implementation:

# House Robber I
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    two_before = nums[0]
    one_before = max(nums[0], nums[1])
    max_value = one_before

    for i in range(2, len(nums)):
        curr_house = nums[i]
        max_value = max(curr_house + two_before, one_before)
        two_before = one_before
        one_before = max_value

    return max_value

# House Robber II
def rob_circle(nums):
    def rob_range(start, end):
        two_before, one_before = 0, 0
        for i in range(start, end + 1):
            curr = max(nums[i] + two_before, one_before)
            two_before = one_before
            one_before = curr
        return one_before

    if len(nums) == 1:
        return nums[0]
    return max(rob_range(0, len(nums) - 2), rob_range(1, len(nums) - 1))

# House Robber III
def rob_tree(root):
    dp = {}

    def dfs(node):
        if not node:
            return 0
        if node in dp:
            return dp[node]

        rob = node.val
        if node.left:
            rob += dfs(node.left.left) + dfs(node.left.right)
        if node.right:
            rob += dfs(node.right.left) + dfs(node.right.right)

        dont_rob = dfs(node.left) + dfs(node.right)
        dp[node] = max(rob, dont_rob)
        return dp[node]

    return dfs(root)
                

C++ Implementation:

// House Robber I
int rob(vector& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    int two_before = nums[0], one_before = max(nums[0], nums[1]), max_value = one_before;

    for (int i = 2; i < nums.size(); ++i) {
        int curr_house = nums[i];
        max_value = max(curr_house + two_before, one_before);
        two_before = one_before;
        one_before = max_value;
    }

    return max_value;
}

// House Robber II
int rob_circle(vector& nums) {
    if (nums.size() == 1) return nums[0];

    auto rob_range = [&](int start, int end) {
        int two_before = 0, one_before = 0;
        for (int i = start; i <= end; ++i) {
            int curr = max(nums[i] + two_before, one_before);
            two_before = one_before;
            one_before = curr;
        }
        return one_before;
    };

    return max(rob_range(0, nums.size() - 2), rob_range(1, nums.size() - 1));
}

// House Robber III
int rob_tree(TreeNode* root) {
    unordered_map dp;

    function dfs = [&](TreeNode* node) {
        if (!node) return 0;
        if (dp.count(node)) return dp[node];

        int rob = node->val;
        if (node->left) rob += dfs(node->left->left) + dfs(node->left->right);
        if (node->right) rob += dfs(node->right->left) + dfs(node->right->right);

        int dont_rob = dfs(node->left) + dfs(node->right);
        dp[node] = max(rob, dont_rob);
        return dp[node];
    };

    return dfs(root);
}