House Robber (LeetCode 198)

The problem

Houses stand in a row and nums[i] is the money in house i (all values non-negative). You cannot rob two adjacent houses in the same night. Return the most money you can take.

Input:  nums = [2, 7, 9, 3, 1]
Output: 12

Rob houses 0, 2 and 4 for 2 + 9 + 1 = 12. Robbing 7 and 3 gives only 10.

How to think about it

Start with brute force. Every house is either robbed or not, so you could try all valid subsets of non-adjacent houses. That is up to O(2ⁿ) choices. Even the recursive version that decides house by house recomputes the same suffixes many times.

The key insight: decide about the current house only. Let dp[i] be the best total using houses 0..i. For house i you have exactly two options. Skip it, and the best is dp[i-1]. Rob it, and the previous house must be untouched, so the best is dp[i-2] + nums[i]. Take the larger: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Two rolling variables. The recurrence only reaches two entries back, so keep prev = dp[i-2] and cur = dp[i-1]. Each step computes the new best and shifts. Starting both at 0 handles the first two houses without special cases.

Which pattern is this? 1-D DP with a take-or-skip choice. The tell is “pick items in a line to maximise a total, with a constraint between neighbours”. Greedy (take the biggest houses) fails because one big house can block two medium ones.

Approach

1. Set prev = 0 and cur = 0 (the best totals two houses back and one house back).
2. For each house value n: the new best is max(cur, prev + n). Shift: prev becomes the old cur, cur becomes the new best.
3. Return cur.

Solution

def rob(nums):
    prev, cur = 0, 0                              # dp[i-2], dp[i-1]
    for n in nums: prev, cur = cur, max(cur, prev + n)   # skip this house, or rob it
    return cur
# rob([2,7,9,3,1]) -> 12  (2 + 9 + 1)

Dry run

On [2, 7, 9, 3, 1], values after processing each house:

The final cur is 12.

Complexity

• Time: O(n). One pass over the houses.
• Space: O(1). Two variables instead of a dp array.

Edge cases and pitfalls

• Empty list returns 0, and one house returns its value; the zero start handles both.
• Updating in the wrong order. Writing prev = cur then cur = max(cur, prev + n) on separate lines uses the new prev. The tuple assignment avoids that.
• Odd/even greedy (sum every other house) fails on inputs like [2, 1, 1, 2], where the best is 4 from the two ends.
• Returning the houses chosen needs the full dp array so you can walk back through the decisions.

Related problems

• House Robber II (LeetCode 213): the same houses arranged in a circle; run this solution twice.
• House Robber III (LeetCode 337): the take-or-skip choice on a binary tree.
• Climbing Stairs (LeetCode 70): the simplest two-rolling-variable DP.