LeetCode 198 - House Robber

This is a Medium DP problem: return the maximum amount that can be robbed without choosing two adjacent houses. At each position, the decision is either rob the current house and skip the next one, or skip the current house and move to the next one.

Problem link and explanation

• Problem link: 198. House Robber
• Summary: Given an integer array nums, return the maximum sum that can be collected without choosing adjacent elements.

For example:

nums = [1, 2, 3, 1]

Choosing the first and third houses gives a total of 4, and those houses are not adjacent. The answer for this input is 4.

Approach

The problem can be described as a choice at each house. If the current index is house and that house is robbed, the next valid index is house + 2. If the current house is skipped, the next index is house + 1.

I defined the recursive function to return the maximum amount that can be collected starting from a given house index.

rec(house) = max(nums[house] + rec(house + 2), rec(house + 1))

The left side of the max represents robbing the current house. The right side represents skipping it. Once house moves past the end of nums, there is nothing left to collect, so the function returns 0.

if house >= len(nums):
    return 0

Without memoization, the recursion keeps branching into two calls. From rec(0), robbing the current house skips house 1 and moves to rec(2). Skipping the current house moves to rec(1). So far, both branches match the problem rule directly.

At rec(1), the same choice happens again. Robbing house 1 moves to rec(3), while skipping house 1 moves to rec(2). That means rec(2) is needed both after “rob house 0 and skip house 1” and after “skip house 0 and skip house 1.”

The same index is therefore computed through multiple paths. As the depth grows, the call tree can almost double at each level, so plain recursion can grow to O(2ⁿ) time. The memo dictionary stores the best result for each house index and returns it immediately after the first calculation.

if house in memo:
    return memo[house]

This keeps the recursive structure while ensuring that each index is solved once.

Complexity analysis

• Time complexity: O(n)

  • With memoization, each house index is computed once.

• Space complexity: O(n)

  • The memo dictionary stores one result per index, and the recursion call stack can also grow linearly in the worst case.

Implementation code

from typing import Dict, List

class Solution:
    def rec(self, house: int, nums: List[int], memo: Dict[int, int]) -> int:
        if house >= len(nums):
            return 0

        if house in memo:
            return memo[house]

        current_robbed = max(
            nums[house] + self.rec(house + 2, nums, memo),
            self.rec(house + 1, nums, memo),
        )
        memo[house] = current_robbed
        return current_robbed

    def rob(self, nums: List[int]) -> int:
        memo: Dict[int, int] = {}
        return self.rec(0, nums, memo)

Summary and reflection

The main step is turning the rob-or-skip decision into a recurrence. Recursion alone repeats the same subproblems, so memoizing by house index turns the solution into top-down DP and keeps the time complexity at O(n).