198. House Robber

Problem Description

You are a robber planning to rob houses along a street. Each house has a certain amount of money. The constraint is that you cannot rob adjacent houses because they have security systems connected. Given an integer array nums representing the amount of money in each house, find the maximum amount of money you can rob without alerting the police.

Solutions

This problem can be solved efficiently using dynamic programming. We'll explore three approaches: Memoization (top-down DP), Dynamic Programming (bottom-up DP), and a space-optimized DP approach.

Solution 1: Memoization (Top-Down DP)

This approach uses recursion with memoization to avoid redundant calculations. A recursive function dfs(i) calculates the maximum robbery amount starting from house i.

• Base Case: If i is out of bounds, return 0 (no more houses to rob).
• Recursive Step: The maximum amount from house i is the maximum of:
  • Robbing house i: nums[i] + dfs(i + 2) (skip the next house due to adjacency constraint)
  • Not robbing house i: dfs(i + 1)

A memoization table (cache) stores the results of dfs(i) to prevent recalculations.

Time Complexity: O(n) - Each house is visited at most once. Space Complexity: O(n) - For the memoization table (cache) and the recursive call stack.

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(nums):
                return 0
            return max(nums[i] + dfs(i + 2), dfs(i + 1))
 
        return dfs(0)

(Similar implementations can be done in Java, C++, Go, JavaScript, TypeScript, and Rust following the same logic, using their respective memoization techniques.)

Solution 2: Dynamic Programming (Bottom-Up DP)

This approach uses an array dp where dp[i] stores the maximum robbery amount considering houses up to index i.

• Base Cases: dp[0] = 0, dp[1] = nums[0]
• Iteration: For i > 1, dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) This represents the choice between robbing or not robbing the current house.

Time Complexity: O(n) - Linear iteration through the houses. Space Complexity: O(n) - For the dp array.

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        return dp[n]

(Similar implementations can be done in other languages, using their respective array structures.)

Solution 3: Space-Optimized Dynamic Programming

We can optimize the space complexity to O(1) by observing that we only need the values of dp[i-1] and dp[i-2] to calculate dp[i]. We can maintain these two values using two variables instead of an array.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev1, prev2 = 0, 0
        for num in nums:
            prev1, prev2 = max(prev1, prev2), prev1 + num
        return max(prev1, prev2)

(Similar space-optimized implementations are possible in other languages.)

Summary

All three approaches solve the House Robber problem correctly. The space-optimized DP offers the best space complexity (O(1)), making it the most efficient solution for large input arrays, while maintaining the linear time complexity of O(n). The choice of which approach to use depends on the specific constraints and preference (readability vs. space efficiency).