LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

House Robber

1d-dp house-robber

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

Example 1
Input: nums = [1,2,3,1]
Output: 4
Rob house 0 (1) + house 2 (3) = 4
Example 2
Input: nums = [2,7,9,3,1]
Output: 12
Rob house 0 (2) + house 2 (9) + house 4 (1) = 12
Key Insight

For each house: either rob it (add to best from 2 houses back) or skip it (take best from 1 house back).

At each house: rob it (add to dp[i-2]) or skip it (keep dp[i-1]). Take the max.

How to Approach This Problem

Pattern Recognition: When you see keywords like house robber 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 At house i, you can:
Answer: A and B both valid
At each house, choose: rob this one (skip i-1) or skip this one (keep i-1's best).
2 If you rob house i, the best you can add to is:
Answer: dp[i-2] (skip i-1)
Can't rob adjacent. So if you rob i, you can only add to best result up to i-2.
3 If you skip house i:
Answer: You get dp[i-1]
Skipping i means the best up to i is same as best up to i-1.
4 dp[i] = ?
Answer: max(nums[i] + dp[i-2], dp[i-1])
Rob house i (nums[i] + dp[i-2]) OR skip it (dp[i-1]). Take max.
5 For one house nums[0]:
Answer: dp[0] = nums[0]
With only one house, rob it.

Solution

def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # prev2 = max profit up to i-2
    # prev1 = max profit up to i-1
    prev2, prev1 = 0, nums[0]
    
    for i in range(1, len(nums)):
        # Rob current (nums[i] + prev2) or skip (prev1)
        curr = max(nums[i] + prev2, prev1)
        prev2 = prev1
        prev1 = curr
    
    return prev1

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye