36. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected, so you cannot rob two adjacent houses. Given an array nums representing the amount of money of each house, return the maximum amount of money you can rob without triggering alarms.

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and house 3 (money = 3) = 1 + 3 = 4.

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12.

Problem Breakdown:

1. At each house, we have two choices: rob it (add its value to what we had two houses ago) or skip it (keep what we had at the previous house). This is the recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

• # dp[i] = max(dp[i-1], dp[i-2] + nums[i])

2. We only need the previous two values, so use two variables instead of an array.

• prev1 = 0  # max money at i-1
  prev2 = 0  # max money at i-2

3. For each house, compute the maximum of skipping (prev1) or robbing (prev2 + current). Update the two variables.

• for num in nums:
      temp = max(prev1, prev2 + num)
      prev2 = prev1
      prev1 = temp

4. After processing all houses, prev1 holds the maximum money.

• return prev1

Summary:

Dynamic programming where at each house you choose to rob it (prev2 + current) or skip it (prev1). Only two variables needed since each state depends only on the previous two. Iterate through all houses and return the maximum.

Time and Space Complexity:

Time Complexity: O(n) - single pass through the array.

Space Complexity: O(1) - only two variables used.

Python Solution:

def rob(nums):
    prev1, prev2 = 0, 0
    for num in nums:
        temp = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = temp
    return prev1

JavaScript Solution:

var rob = function(nums) {
    let prev1 = 0, prev2 = 0;
    for (const num of nums) {
        const temp = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
};

Java Solution:

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