0198.House Robber

• Link: 198. House Robber - Medium
• Track: NeetCode150

Question

• Example 1:
  • Input: nums = [1,2,3,1]
  • Output: 4
  • Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Restate the problem

• Given an integer array nums where nums[i] is the money in house i
• You cannot rob two adjacent houses
• Return the maximum money you can rob

Edge Case

• Base case: n == 1 → return nums[0]
• Base case:n == 2 → return max(nums[0], nums[1])

---

Method	Approach	Time Complexity	Space Complexity
Method 1	DP	$O(n)$	$O(n)$
Method 2 ⭐	DP (No extra space)	$O(n)$	$O(1)$

Method 1 - DP

Key idea: Let dp[i] be the maximum money you can rob from houses [0..i].
从左到右，每一间房只有两种选择：不偷=dp[i−1]，偷=dp[i−2]+nums[i]，取最大值即可。

Approach

1. If n == 1, return nums[0]
2. Build dp:
   • dp[0] = nums[0]
   • dp[1] = max(nums[0], nums[1])
3. For i from 2 to n-1:
   • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
4. Return dp[n-1]

Complexity

• Time Complexity: $O(n)$
• Space Complexity:$O(n)$

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[1]
        
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = nums[1]
        
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        
        return dp[-1]

Method 2 - DP (No extra space)

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        prev2 = 0
        prev1 = 0
        for num in nums:
            cur = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = cur
        
        return prev1

---

Mistake

• dp[1]= max(nums[0], nums[1])
• method2: Rolling DP update order wrong (overwriting prev2/prev1 too early) → compute cur first, then shift