House Robber: Pick or Skip DP Pattern

Learning Outcome

After this lesson, you should be able to model adjacent restrictions with a pick-or-skip recurrence.

Problem Statement

Given money in a row of houses, return the maximum amount you can rob without robbing adjacent houses.

Brute Force Approach

Try every subset and reject subsets with adjacent houses. This grows exponentially.

Optimized Approach

For each house, choose max(skip current, rob current plus best before previous). Keep two rolling best values.

Exact Pseudocode

prev2 = 0
prev1 = 0
for money in nums:
  current = max(prev1, prev2 + money)
  prev2 = prev1
  prev1 = current
return prev1
  

Reference Code

class Solution:
    def rob(self, nums):
        prev2 = 0
        prev1 = 0

        for money in nums:
            current = max(prev1, prev2 + money)
            prev2 = prev1
            prev1 = current

        return prev1
  

Sample Dry Run

Complexity

Edge Cases

• Empty input should return 0.
• Single house returns that house value.
• Do not rob adjacent houses even if both are large.

Interview Checklist

• Separate skip-current and take-current choices.
• Use the old prev1 before overwriting prev2.
• Return the best up to the last house.

FAQs

It is the best value up to the previous house.

It is the best value up to the house before the previous one.

Pick-or-skip DP.