House Robber

How it works

We don’t actually need a full DP array.

At any house, we only care about:

• the best result up to the previous house
• the best result up to the house before that

So instead of storing everything, we just keep two variables and update them as we move forward.

For each house:

• Either skip it → keep previous best
• Or rob it → current money + best from two steps back
  Pick the maximum.

Steps

1. Initialize two variables:
   • rob1 → best up to house i - 2
   • rob2 → best up to house i - 1
2. For each house value:
   • Compute newRob = max(rob2, rob1 + currentHouseValue)
   • Move pointers:
     • rob1 = rob2
     • rob2 = newRob
3. After processing all houses, rob2 is the answer.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Incorrect Base Case Initialization

In the bottom-up DP approach, dp[1] should be initialized as max(nums[0], nums[1]), not just nums[1]. This represents the maximum money obtainable from the first two houses. If you set dp[1] = nums[1], you ignore the possibility that the first house might have more money, leading to suboptimal results.

Confusing the Recurrence Relation

The recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]) represents choosing between skipping house i (keeping the best from i-1) or robbing house i (adding its value to the best from i-2). A common mistake is writing dp[i] = max(dp[i-1] + nums[i], dp[i-2]), which incorrectly adds the current house value when skipping it. Remember: robbing requires jumping over the previous house, not adding to it.

Not Handling Edge Cases for Empty or Single-Element Arrays

When the input array is empty, return 0. When it has only one element, return that element. The bottom-up approach with a DP array requires at least two elements to initialize dp[0] and dp[1]. Failing to handle these edge cases causes index-out-of-bounds errors or incorrect results. The space-optimized solution with two variables naturally handles the single-element case but still needs an empty array check.

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for num in nums:
            temp = max(num + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2

class Solution {
public:
    int rob(vector<int>& nums) {
        int rob1 = 0, rob2 = 0;

        for (int num : nums) {
            int temp = max(num + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
};