This problem follows the Decision DP pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Rob current or skip.
At each house, the optimal choice only depends on the last two results — this 'rolling' technique reduces O(n) space to O(1).
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1Practice House Robber and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.
Practice this problem