You are a robber. Given an array of house values, find the maximum money you can rob without robbing two adjacent houses.
At each house you make one choice: rob it (and skip the previous) or skip it (and carry forward whatever you had). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Since you only look back two steps, two variables replace the full array, giving O(n) time and O(1) space.
How to think about it
Recognise the pattern
The signal is a linear sequence with a “skip one neighbour” constraint. Whenever a decision at index i affects what you can do at i+1 but not i+2, the recurrence has a clean two-state look-back. This pattern appears in stock cooldown, paint houses, and delete-and-earn problems — all are house-robber variants in disguise.
Define the DP
- State:
dp[i]= maximum money robbing optimally among houses 0 … i. - Recurrence:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])dp[i-1]: skip house i, keep whatever was best up to i-1.dp[i-2] + nums[i]: rob house i, add its value to the best before the previous house.
- Base cases:
dp[0] = nums[0],dp[1] = max(nums[0], nums[1]).
Build the approach step by step
Brute force tries every subset of non-adjacent houses — exponential.
Recursive with memo is clean but O(n) stack space.
Bottom-up, space-optimised: since dp[i] only depends on dp[i-1] and dp[i-2], keep only prev2 and prev1:
nums = [2, 7, 9, 3, 1]
i=0: prev2=2
i=1: prev1=max(2,7)=7
i=2: new = max(7, 2+9) = 11 prev2=7, prev1=11
i=3: new = max(11, 7+3) = 11 prev2=11, prev1=11
i=4: new = max(11, 11+1) = 12 prev2=11, prev1=12
Answer: 12 (rob houses 0,2,4 -> 2+9+1=12)Complexity
- Time — O(n): one pass through the array.
- Space — O(1): two variables, no array.