LeetCode 198: House Robber

Problem Restatement

We are given an integer array nums.

Each element represents the amount of money inside one house.

A robber wants to steal as much money as possible, but there is one restriction:

Two adjacent houses cannot both be robbed.

If two adjacent houses are robbed on the same night, the alarm system activates.

We need to return the maximum amount of money that can be robbed without triggering the alarm. The official problem asks for the maximum amount of money that can be robbed without robbing adjacent houses.

Input and Output

Example function shape:

def rob(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3, 1]

Possible choices:

The best valid choice is:

1 + 3 = 4

Answer:

4

Example 2:

nums = [2, 7, 9, 3, 1]

One good plan:

2 + 9 + 1 = 12

Answer:

12

First Thought: Try Every Combination

For every house, we have two choices:

This creates many possible combinations.

For example:

[2, 7, 9, 3]

We might choose:

2 + 9
7 + 3
2 + 3
9
...

The number of possibilities grows exponentially.

We need a way to reuse previous results.

Key Insight

At each house, there are only two meaningful possibilities:

Suppose we are at house i.

If we rob house i, then house i - 1 cannot be robbed.

So the total becomes:

nums[i] + best(i - 2)

If we skip house i, then the total becomes:

best(i - 1)

So the recurrence is:

This is the core dynamic programming relation.

Algorithm

1. If there are no houses, return 0.
2. If there is one house, return its value.
3. Use dynamic programming.
4. For each house:
   • Either skip it.
   • Or rob it and add the best answer from two houses earlier.
5. Return the final maximum value.

Building the DP Table

Let:

dp[i]

mean:

Maximum money we can rob from houses 0..i

Base cases:

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Then for every later house:

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

Correctness

For each house i, every valid robbery plan falls into one of two categories:

No valid plan exists outside these two cases.

The recurrence chooses the better of them.

So dp[i] correctly stores the maximum robbery amount for houses 0..i.

By induction, every DP state is correct, so the final result dp[n - 1] is also correct.

Complexity

Here, n is the number of houses.

Implementation

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)

        if n == 0:
            return 0

        if n == 1:
            return nums[0]

        dp = [0] * n

        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

        return dp[-1]

Code Explanation

This handles the empty array case:

if n == 0:
    return 0

This handles a single house:

if n == 1:
    return nums[0]

We create the DP array:

dp = [0] * n

This initializes the first house result:

dp[0] = nums[0]

For two houses, we choose the larger value:

dp[1] = max(nums[0], nums[1])

Then we fill the remaining states:

for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

Finally:

return dp[-1]

returns the best possible robbery amount.

Space Optimization

Notice that:

dp[i]

depends only on:

dp[i - 1]
dp[i - 2]

So we do not need the full array.

We can keep only two variables.

Optimized Implementation

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0
        prev1 = 0

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

            prev2 = prev1
            prev1 = current

        return prev1

Here:

This reduces space complexity to O(1).

Testing

def run_tests():
    s = Solution()

    assert s.rob([1, 2, 3, 1]) == 4
    assert s.rob([2, 7, 9, 3, 1]) == 12
    assert s.rob([1]) == 1
    assert s.rob([2, 1, 1, 2]) == 4
    assert s.rob([0]) == 0
    assert s.rob([5, 1, 1, 5]) == 10

    print("all tests passed")

run_tests()

Test meaning: