198. House Robber

Problem¶

Given a list nums, where nums[i] is the money in house i, return the maximum money you can take if you cannot rob two adjacent houses.

• Example:
• Input: nums = [2, 7, 9, 3, 1]
• Output: 12
• Best choice: rob houses with 2 + 9 + 1

Key trick¶

Use dynamic programming with only two running values:

• prev2 = best answer up to house i - 2
• prev1 = best answer up to house i - 1

For each house x, the transition is:

Trap¶

Common mistakes:

• Using recursion on slices, which is exponential and creates extra arrays.
• Forgetting that robbing the current house forces skipping the previous one.
• Overcomplicating base cases instead of using the rolling DP pattern.

Why is it interesting?¶

It is a small but classic DP problem:

• It tests whether you can turn a choice of "take or skip" into a recurrence.
• It also rewards noticing that the full DP array is unnecessary.

Python solution¶

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0 # best total up to two houses ago
        prev1 = 0 # best total up to previous house

        for money in nums:
            # Either skip this house, or rob it and add prev2
            prev2, prev1 = prev1, max(prev1, prev2 + money)

        return prev1

Comment on my solution¶

Your solution should be replaced.

Problems:

• It uses recursion with slicing, which is very slow.
• Its time is exponential, and slicing adds extra \(O(n)\) overhead per call.

A good interview solution should be iterative DP in \(O(n)\) time and \(O(1)\) space.

import pytest

class Solution:
    def rob(self, nums: list[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        mid = len(nums) // 2
        skipping_mid = self.rob(nums[:mid]) + self.rob(nums[mid + 1:])
        keeping_mid = self.rob(nums[:mid - 1]) + self.rob(nums[mid:])
        return max(skipping_mid, keeping_mid)

@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1,2,3,1], 4),
        ([2,7,9,3,1], 12),
        ([3,1,3,1,1,3,1], 9)
    ]
)
def test_rob(nums, expected):
    assert Solution().rob(nums) == expected