House Robber (LC 198)

Pattern: Dynamic Programming - Linear (Fibonacci-style)
Difficulty: Medium
Key Concept: “Maximize total, but cannot pick adjacent elements”

Problem Statement

You are a thief planning to rob houses along a street. Each house has money. You cannot rob two adjacent houses (security system). Maximize your total loot.

Example: houses = [2, 7, 9, 3, 1] → Answer: 12 (rob houses 0, 2, 4: 2+9+1)

---

The Decision Logic

At every house i, you choose:

1. Rob it: Get houses[i] + best loot from i-2 (skipped previous house)
2. Skip it: Keep best loot from i-1

$$DP[i] = \max(DP[i-1], ; houses[i] + DP[i-2])$$

---

Brute Force: Recursive - O(2^n)

class Solution {
    public int rob(int[] nums) {
        return helper(nums, nums.length - 1);
    }

    private int helper(int[] nums, int i) {
        if (i < 0) return 0;
        return Math.max(
            helper(nums, i - 1),
            nums[i] + helper(nums, i - 2)
        );
    }
}

---

Optimal: Space-Optimized DP - O(n) time, O(1) space

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        int prev2 = 0;
        int prev1 = 0;

        for (int num : nums) {
            int current = Math.max(prev1, num + prev2);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

---

Dry Run

Houses: [2, 7, 9, 3, 1]

House 0 (val=2): max(prev1=0, 2+prev2=0) = 2    → prev2=0, prev1=2
House 1 (val=7): max(prev1=2, 7+prev2=0) = 7    → prev2=2, prev1=7
House 2 (val=9): max(prev1=7, 9+prev2=2) = 11   → prev2=7, prev1=11
House 3 (val=3): max(prev1=11, 3+prev2=7) = 11  → prev2=11, prev1=11
House 4 (val=1): max(prev1=11, 1+prev2=11) = 12 → prev2=11, prev1=12

Answer: 12

---

Pattern Recognition

Whenever a problem says “Maximize X, but you cannot pick adjacent elements,” it is a House Robber variation.

---

Complexity

Approach	Time	Space
Recursive	O(2^n)	O(n)
Memoized	O(n)	O(n)
Tabulated	O(n)	O(n)
Space-Optimized	O(n)	O(1)