Problem #198: House Robber

Intuition & Strategy Breakdown

Use dynamic programming. dp[i] = max(dp[i-1], dp[i-2] + nums[i]), maintaining two variables for space optimization.

Python Solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0
        
        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp
            
        return rob2

Java Solution

class Solution {
    public int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;
        for (int n : nums) {
            int temp = Math.max(n + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}