House Robber medium

Problem Statement

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 a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 1). Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Steps and Explanation

This problem can be solved using dynamic programming. The core idea is that to determine the maximum amount of money you can rob up to a given house, you only need to consider two options:

1. Rob the current house: In this case, you cannot rob the previous house. The maximum amount you can rob is the current house's value plus the maximum amount you could rob up to two houses before.
2. Don't rob the current house: In this case, the maximum amount you can rob is simply the maximum amount you could rob up to the previous house.

We can build a DP table (or array) to store these maximum amounts.

Let dp[i] represent the maximum amount of money that can be robbed up to house i. Then:

• dp[0] = nums[0] (If there's only one house, rob it)
• dp[1] = max(nums[0], nums[1]) (If there are two houses, rob the one with more money)
• dp[i] = max(nums[i] + dp[i-2], dp[i-1]) for i >= 2

Code (Python)

def rob(nums):
    """
    :type nums: List[int]
    :rtype: 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(nums[i] + dp[i-2], dp[i-1])

    return dp[n-1]

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the nums array once.
• Space Complexity: O(n) in the worst case. We use a DP array of size n. This could be optimized to O(1) by only keeping track of the two most recent maximum amounts instead of the entire array. Here's an optimized version:

Optimized Code (Python) - O(1) Space

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])

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

    return prev2

This optimized version achieves the same result with constant space complexity.