House Robber Problem

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Naive Approach (Brute Force)

A brute force approach would involve trying all possible combinations of robbing houses and finding the combination that yields the maximum amount without robbing adjacent houses. This can be done using recursion.

1. For each house, we have two choices: rob it or don't rob it.
2. If we rob the current house, we cannot rob the next house.
3. If we don't rob the current house, we can consider the next house.

This approach leads to overlapping subproblems and is highly inefficient.

Code (Python - Naive)

def rob_recursive(nums):
    def rob(i):
        if i >= len(nums):
            return 0
        # Rob current house + skip the next
        rob_current = nums[i] + rob(i + 2)
        # Don't rob current house
        skip_current = rob(i + 1)
        return max(rob_current, skip_current)

    return rob(0)

Time Complexity

O(2ⁿ), where n is the number of houses.

Space Complexity

O(n) due to the recursion depth.

Optimal Approach (Dynamic Programming)

The optimal approach uses dynamic programming to avoid recomputation of overlapping subproblems.

1. Create a DP array dp where dp[i] represents the maximum amount that can be robbed up to house i.
2. dp[0] = nums[0] (If there is only one house, rob it).
3. dp[1] = max(nums[0], nums[1]) (If there are two houses, rob the one with maximum amount).
4. For i > 1, dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
   • dp[i-1] means we don't rob house i.
   • dp[i-2] + nums[i] means we rob house i and the maximum amount up to i-2.
5. The final result is dp[n-1], where n is the number of houses.

Code (Python - Dynamic Programming)

def rob(nums):
    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[n - 1]

Alternatively, we can optimize space complexity to O(1) by storing only the last two values.

def rob_optimized(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    prev1 = nums[0]
    prev2 = max(nums[0], nums[1]) if n > 1 else nums[0]

    for i in range(2, n):
        current = max(prev2, prev1 + nums[i])
        prev1 = prev2
        prev2 = current

    return prev2

Time Complexity

O(n), where n is the number of houses.

Space Complexity

O(n) for the DP array in the first DP solution. O(1) for the space-optimized version.

Edge Cases

1. Empty input array: return 0.
2. Single house: return the amount in that house.
3. Two houses: return the maximum of the two houses.

Summary

The dynamic programming approach provides an efficient solution with a time complexity of O(n) and a space complexity of O(n) which can be further optimized to O(1). It avoids the exponential time complexity of the naive recursive approach by storing and reusing intermediate results.