Problem Description

You are planning to rob houses along a street where each house contains a certain amount of money. The constraint is that adjacent houses have connected security systems - if you rob two adjacent houses on the same night, the police will be alerted.

Given an integer array nums where nums[i] represents the amount of money in the i-th house, you need to determine the maximum amount of money you can rob without triggering the security system (i.e., without robbing two adjacent houses).

For example:

• If nums = [2, 7, 9, 3, 1], you can rob houses at index 0, 2, and 4 to get 2 + 9 + 1 = 12, or rob houses at index 1 and 3 to get 7 + 3 = 10. The maximum is 12.
• You cannot rob houses at index 1 and 2 together since they are adjacent.

The solution uses a recursive approach with memoization. The function dfs(i) calculates the maximum money that can be robbed starting from house i. At each house, you have two choices:

1. Rob the current house and skip the next one: nums[i] + dfs(i + 2)
2. Skip the current house and consider the next one: dfs(i + 1)

The maximum of these two choices gives the optimal solution. The @cache decorator prevents recalculating the same subproblems, improving efficiency from exponential to linear time complexity.

Intuition

The key insight is that at each house, we face a decision: rob it or skip it. This naturally leads to a recursive thinking pattern.

If we rob the current house, we must skip the next house due to the security system, so we can only consider robbing from the house two positions ahead. If we skip the current house, we can immediately consider the next house.

This creates a decision tree where each node represents choosing to rob or not rob a particular house. The problem becomes finding the path through this tree that maximizes our total money.

Notice that when we're at position i, the maximum money we can get depends only on the choices available from position i onwards - it doesn't matter how we got to position i. This is the optimal substructure property that makes dynamic programming applicable.

The recursive relationship emerges naturally: for any house at position i, the maximum money is the better of two options:

• nums[i] + dfs(i + 2): Rob this house and add the maximum possible from houses starting at i + 2
• dfs(i + 1): Skip this house and take the maximum possible from houses starting at i + 1

Since we'll encounter the same positions multiple times through different paths (for example, we can reach position 3 by skipping houses 1 and 2, or by robbing house 1 and skipping house 2), memoization prevents redundant calculations by storing results of each position we've already computed.

Solution Approach

The solution implements a top-down dynamic programming approach using memoization search. Here's how the implementation works:

We define a recursive function dfs(i) that represents the maximum amount of money that can be robbed starting from the i-th house. The answer to our problem is dfs(0) - the maximum money starting from the first house.

The function follows this logic:

• Base case: If i >= len(nums), we've gone past all houses, so return 0
• Recursive case: We have two choices:
  • Rob the current house: Get nums[i] money and continue from house i + 2 (skipping the adjacent house)
  • Skip the current house: Continue from house i + 1
  • Return the maximum of these two options: max(nums[i] + dfs(i + 2), dfs(i + 1))

The @cache decorator (from Python's functools) automatically memoizes the function results. When dfs(i) is called:

1. First check if the result for i has been computed before
2. If yes, return the cached result immediately
3. If no, compute the result, cache it, and return it

This memoization transforms what would be an exponential time complexity (due to overlapping subproblems) into linear time complexity O(n), where each house position is computed exactly once.

The space complexity is O(n) for the recursion stack and the cache storing results for each position.

The recursion tree for nums = [2, 7, 9, 3, 1] would start with dfs(0), which branches into dfs(1) (skip house 0) and dfs(2) (rob house 0), and continues until reaching the base cases where i >= 5.

Example Walkthrough

Let's walk through a small example with nums = [2, 7, 9, 3, 1] to illustrate how the recursive solution with memoization works.

Starting with dfs(0), we need to decide whether to rob house 0 or skip it:

Step 1: dfs(0)

• Option 1: Rob house 0 → Get 2 + dfs(2)
• Option 2: Skip house 0 → Get dfs(1)
• We need to evaluate both options

Step 2: Evaluate dfs(1) (from skipping house 0)

• Option 1: Rob house 1 → Get 7 + dfs(3)
• Option 2: Skip house 1 → Get dfs(2)

Step 3: Evaluate dfs(2) (appears in multiple paths)

• Option 1: Rob house 2 → Get 9 + dfs(4)
• Option 2: Skip house 2 → Get dfs(3)
• Note: This result gets cached after first computation

Step 4: Evaluate dfs(3)

• Option 1: Rob house 3 → Get 3 + dfs(5)
• Option 2: Skip house 3 → Get dfs(4)

Step 5: Evaluate dfs(4)

• Option 1: Rob house 4 → Get 1 + dfs(6)
• Option 2: Skip house 4 → Get dfs(5)

Step 6: Base cases

• dfs(5) = 0 (no more houses)
• dfs(6) = 0 (no more houses)

Working backwards with computed values:

• dfs(4) = max(1 + 0, 0) = 1
• dfs(3) = max(3 + 0, 1) = 3
• dfs(2) = max(9 + 1, 3) = 10 (cached for reuse)
• dfs(1) = max(7 + 3, 10) = 10
• dfs(0) = max(2 + 10, 10) = 12

The maximum money we can rob is 12 by robbing houses at indices 0, 2, and 4 (values: 2, 9, and 1).

The memoization ensures that when dfs(2) is called again (from the path where we robbed house 0), we immediately return the cached value of 10 instead of recalculating the entire subtree.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the nums array. Although the recursive function appears to have overlapping subproblems that could lead to exponential time complexity, the @cache decorator memoizes the results. Each unique state i from 0 to n-1 is computed exactly once, and each computation takes O(1) time to execute the max operation and lookups.

The space complexity is O(n), where n is the length of the nums array. This comes from two sources:

1. The cache storage: The @cache decorator stores up to n unique results (one for each possible value of i from 0 to n-1), requiring O(n) space.
2. The recursion call stack: In the worst case, the recursion depth can go up to n levels deep (when always choosing dfs(i + 1)), requiring O(n) space for the call stack.

Therefore, the total space complexity is O(n) + O(n) = O(n).

Common Pitfalls

1. Stack Overflow for Large Inputs

The recursive solution with memoization can cause stack overflow when the input array is very large (typically around 1000+ elements in Python). Python has a default recursion limit, and deep recursion can exceed this limit.

Why it happens: Each recursive call adds a frame to the call stack. For an array of size n, the worst-case recursion depth is n when we keep skipping houses.

Solution: Convert to iterative dynamic programming or increase recursion limit:

# Option 1: Iterative DP (Recommended)
def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
  
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
  
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], nums[i] + dp[i-2])
  
    return dp[-1]

# Option 2: Space-optimized iterative
def rob(self, nums: List[int]) -> int:
    prev2 = prev1 = 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

# Option 3: Increase recursion limit (Not recommended for production)
import sys
sys.setrecursionlimit(10000)

2. Forgetting to Handle Edge Cases

The recursive solution assumes valid input, but edge cases can break the logic.

Common edge cases:

• Empty array: nums = []
• Single element: nums = [5]
• All zeros: nums = [0, 0, 0]
• Negative numbers (if problem allows)

Solution: Add input validation:

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
  
    @cache
    def dfs(index: int) -> int:
        # ... rest of the code

3. Memory Issues with @cache Decorator

The @cache decorator stores all computed results indefinitely, which can cause memory issues if the function is called multiple times with different inputs in the same program execution.

Why it happens: The cache persists between function calls and never clears automatically.

Solution: Use lru_cache with maxsize or clear cache manually:

from functools import lru_cache

class Solution:
    def rob(self, nums: List[int]) -> int:
        @lru_cache(maxsize=None)  # Can set maxsize=128 for memory limit
        def dfs(index: int) -> int:
            # ... implementation
      
        result = dfs(0)
        dfs.cache_clear()  # Clear cache after getting result
        return result

4. Index Confusion in Recursion

A common mistake is using wrong indices in the recursive calls, such as dfs(i + 1) vs dfs(i + 2), or comparing i > len(nums) instead of i >= len(nums).

Solution: Clearly document what each index represents and use consistent naming:

def dfs(current_house: int) -> int:
    # Clear naming helps avoid confusion
    if current_house >= len(nums):
        return 0
  
    rob_this_house = nums[current_house] + dfs(current_house + 2)
    skip_this_house = dfs(current_house + 1)
  
    return max(rob_this_house, skip_this_house)