Problem Statement
House Robber
Imagine a row of houses on a street, each with some cash inside. You want to grab as much money as you can. The catch: every house's alarm is wired to its next-door neighbor, so if you rob two houses that sit right next to each other, the alarm goes off. You are given an array (a numbered list of values) called nums, where each number is the cash in one house. Return the largest total you can take without ever robbing two houses that are side by side.
Signals to notice
Brute force first
Try all subsets of non-adjacent houses. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — rob this house or skip it. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on nums=[2,7,9,3,1]
start: prev1=0, prev2=0 num=2: temp=max(0, 0+2)=2 -> prev2=0, prev1=2 num=7: temp=max(2, 0+7)=7 -> prev2=2, prev1=7 num=9: temp=max(7, 2+9)=11 (rob) -> prev2=7, prev1=11 num=3: temp=max(11, 7+3)=11 (skip) -> prev2=11, prev1=11 num=1: temp=max(11, 11+1)=12 (rob) -> prev2=11, prev1=12 return prev1 = 12
What must stay true
At each house, the best choice is the better of: skip (keep previous max) or rob (add to max from two back). If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
prev1, prev2 = 0, 0 # best incl. last two houses
for num in nums:
take = prev2 + num # rob this house
prev1, prev2 = max(prev1, take), prev1
return prev1Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Forgetting that you CAN skip multiple houses — dp[i-1] already accounts for that. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.