198. House Robber

Reformulated question¶

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:

\[ dp[i] = \max(dp[i-1], dp[i-2] + x) \]

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 this question 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.

Solve the problem with idiomatic python¶

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

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

        return prev1

Pytest test¶

import pytest

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

Comment 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