House Robber Series

The House Robber family is the classic take-or-skip linear DP pattern: at each house you either rob it (and skip the neighbor) or skip it (and keep the best from before). Variants extend this to a circular street, a binary tree, and grouped rewards. This lesson covers House Robber I–III (LeetCode 198, 213, 337), Delete and Earn (740), and solutions in C, Java, and Python with trace tables.

Overview — Take or Skip

Each house has a non-negative loot value. You cannot rob two adjacent houses. Maximize total loot.

Linear street:  [2] — [7] — [9] — [3] — [1]
                 ↑ rob   skip  rob   skip  rob  → 2 + 9 + 1 = 12

At index i:
  rob  = nums[i] + best up to i-2
  skip = best up to i-1
  dp[i] = max(rob, skip)

Rolling form: prev2, prev1 — same as Fibonacci-style 1D DP

House Robber I — Linear Street

Problem (LeetCode 198): Given nums[i] = money in house i, return maximum loot without robbing adjacent houses.

Recurrence: dp[i] = max(dp[i−1], dp[i−2] + nums[i])

Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

Complexity: O(n) time, O(1) space with rolling variables.

House Robber I Code (C, Java, Python)

Python

def rob(nums):
    """LeetCode 198 — max loot, no adjacent houses. O(n) time, O(1) space."""
    prev2, prev1 = 0, 0
    for num in nums:
        take = prev2 + num
        skip = prev1
        prev2, prev1 = prev1, max(take, skip)
    return prev1


if __name__ == "__main__":
    tests = [[2, 7, 9, 3, 1], [1, 2, 3, 1], [2, 1, 1, 2]]
    for nums in tests:
        print(f"rob({nums}) → {rob(nums)}")

Java

public class HouseRobberI {

    /** Rolling prev2 / prev1 — no adjacent robbery. */
    public static int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int take = prev2 + num;
            int skip = prev1;
            prev2 = prev1;
            prev1 = Math.max(take, skip);
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 7, 9, 3, 1})); // 12
        System.out.println(rob(new int[]{1, 2, 3, 1}));     // 4
        System.out.println(rob(new int[]{2, 1, 1, 2}));     // 4
    }
}

C

#include <stdio.h>

int max2(int a, int b) { return a > b ? a : b; }

int rob(int nums[], int n) {
    int prev2 = 0, prev1 = 0, i;
    for (i = 0; i < n; i++) {
        int take = prev2 + nums[i];
        int skip = prev1;
        prev2 = prev1;
        prev1 = max2(take, skip);
    }
    return prev1;
}

int main(void) {
    int a[] = {2, 7, 9, 3, 1};
    int b[] = {1, 2, 3, 1};
    printf("%d\n", rob(a, 5)); /* 12 */
    printf("%d\n", rob(b, 4)); /* 4 */
    return 0;
}

House Robber I Output & Trace

Program output

Rolling trace for [2, 7, 9, 3, 1]

Space Optimization

Only the last two decisions matter — use prev2 and prev1 instead of a full dp[] array. The same trick applies to climbing stairs and other 1D recurrences.

def rob_tabulation(nums):
    """LeetCode 198 — explicit dp[] for whiteboard clarity."""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

House Robber II — Circular Street

Problem (LeetCode 213): Houses are arranged in a circle — the first and last houses are neighbors. You cannot rob both.

Insight: Optimal solution either excludes house 0 or excludes house n−1. Run House Robber I twice:

• On nums[0 .. n−2] (skip last house)
• On nums[1 .. n−1] (skip first house)

Return the maximum of the two. Edge case: if n == 1, return nums[0].

House Robber II Code (C, Java, Python)

Python

def rob_linear(nums):
    """Helper — House Robber I on a slice."""
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1


def rob_circular(nums):
    """LeetCode 213 — circular street."""
    if len(nums) == 1:
        return nums[0]
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))


if __name__ == "__main__":
    print(rob_circular([2, 3, 2]))       # 3
    print(rob_circular([1, 2, 3, 1]))   # 4
    print(rob_circular([1, 2, 3]))      # 3

Java

public class HouseRobberII {

    private static int robLinear(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int take = prev2 + nums[i];
            int skip = prev1;
            prev2 = prev1;
            prev1 = Math.max(take, skip);
        }
        return prev1;
    }

    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(
            robLinear(nums, 0, nums.length - 2),
            robLinear(nums, 1, nums.length - 1)
        );
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2}));     // 3
        System.out.println(rob(new int[]{1, 2, 3, 1}));   // 4
    }
}

C

#include <stdio.h>

int max2(int a, int b) { return a > b ? a : b; }

int rob_range(int nums[], int start, int end) {
    int prev2 = 0, prev1 = 0, i;
    for (i = start; i <= end; i++) {
        int take = prev2 + nums[i];
        int skip = prev1;
        prev2 = prev1;
        prev1 = max2(take, skip);
    }
    return prev1;
}

int rob_circular(int nums[], int n) {
    if (n == 1) return nums[0];
    return max2(rob_range(nums, 0, n - 2), rob_range(nums, 1, n - 1));
}

int main(void) {
    int a[] = {2, 3, 2};
    int b[] = {1, 2, 3, 1};
    printf("%d\n", rob_circular(a, 3)); /* 3 */
    printf("%d\n", rob_circular(b, 4)); /* 4 */
    return 0;
}

House Robber II Output & Trace

House Robber III — Binary Tree

Problem (LeetCode 337): Each tree node has a value. You cannot rob two directly connected nodes. Return maximum loot.

Tree DP: For each node return a pair (rob_this, skip_this):

• rob = node.val + left.skip + right.skip
• skip = max(left.rob, left.skip) + max(right.rob, right.skip)

Post-order DFS — children must be resolved before the parent. Answer: max(root.rob, root.skip).

       3
      / \
     2   3
      \   \
       3   1

Rob {3, 1, 3} = 7  (skip node 3 at root, take leaves)
Skip root 3 → best from subtrees

House Robber III Code (Python, Java)

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def rob_tree(root):
    """LeetCode 337 — post-order (rob, skip) per node."""

    def dfs(node):
        if not node:
            return 0, 0  # rob, skip
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
        rob = node.val + left_skip + right_skip
        skip = max(left_rob, left_skip) + max(right_rob, right_skip)
        return rob, skip

    return max(dfs(root))


# Tree: [3,2,3,null,3,null,1] → 7
if __name__ == "__main__":
    root = TreeNode(3,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(3, None, TreeNode(1)))
    print(rob_tree(root))  # 7

Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class HouseRobberIII {

    /** Returns int[2]: {rob this node, skip this node}. */
    private static int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = node.val + left[1] + right[1];
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, skip};
    }

    public static int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        System.out.println(rob(root)); // 7
    }
}

Tree trace for [3,2,3,null,3,null,1]

Delete and Earn & Related Variants

Delete and Earn (740): Pick a number num, earn all copies of it, but you cannot pick num−1 or num+1. Sort values, group totals per number, then run House Robber I on the grouped array.

def delete_and_earn(nums):
    """LeetCode 740 — reduce to house robber on value line."""
    if not nums:
        return 0
    max_val = max(nums)
    points = [0] * (max_val + 1)
    for num in nums:
        points[num] += num
    prev2, prev1 = 0, 0
    for p in points:
        prev2, prev1 = prev1, max(prev1, prev2 + p)
    return prev1

Connection to Fibonacci / Climbing Stairs

House Robber I with all houses worth 1 is equivalent to counting ways to pick non-adjacent positions — closely related to Fibonacci and climbing stairs. The rolling prev2, prev1 pattern appears in both:

Approach Comparison

Real-Life Applications

Interview Tips

1. State recurrence first: dp[i] = max(dp[i−1], dp[i−2] + nums[i]).
2. Trace [2,7,9,3,1] → 12 on the whiteboard before coding.
3. Offer O(n) array, then compress to prev2/prev1.
4. For II: explain why splitting at first/last covers all valid circular solutions.
5. For III: return two values per node — rob vs skip — post-order DFS.
6. Don't confuse with knapsack (subset with weight limit) — robber has order and adjacency only.
7. Delete and Earn: mention sorting/grouping reduction to Robber I.
8. Link to climbing stairs for the shared rolling-DP skeleton.