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 = 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 = 2 + 9 + 1 = 12.

Steps

The problem can be solved using dynamic programming. We can create a DP array where dp[i] represents the maximum amount of money that can be robbed up to house i. There are two choices at each house:

1. Rob the current house: In this case, we add the current house's money to the maximum amount robbed from houses up to i-2 (since we can't rob adjacent houses).
2. Don't rob the current house: In this case, the maximum amount robbed is the same as the maximum amount robbed up to house i-1.

We take the maximum of these two choices for each house.

Explanation

Let's trace the example nums = [2,7,9,3,1].

• dp[0] = 2 (rob only the first house)
• dp[1] = max(2, 7) = 7 (rob the second house, or don't rob the second house and keep the amount from the first)
• dp[2] = max(7, 2 + 9) = 11 (rob the third house, adding its value to the maximum from the first house, or don't rob the third house and keep the amount from the second)
• dp[3] = max(11, 7 + 3) = 11 (rob the fourth, adding its value to the second house, or don't rob it and keep from the third)
• dp[4] = max(11, 11 + 1) = 12 (rob the fifth, adding its value to the maximum from the third house, or don't rob it and keep from the fourth)

Therefore, the maximum amount is 12.

Code

public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }

        int n = nums.Length;
        if (n == 1) {
            return nums[0];
        }

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the array once.
• Space Complexity: O(n), due to the DP array. This can be optimized to O(1) by only storing the previous two maximum amounts instead of the entire array. (See Optimized Code below)

Optimized Code (O(1) Space)

public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }

        int n = nums.Length;
        if (n == 1) {
            return nums[0];
        }

        int prevMax = nums[0];
        int currMax = Math.Max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            int temp = currMax;
            currMax = Math.Max(currMax, prevMax + nums[i]);
            prevMax = temp;
        }

        return currMax;
    }
}

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