Solution For House Robber

The House Robber problem on LeetCode is a dynamic programming problem. The problem statement is as follows:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses will 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.

To solve this problem, we need to use dynamic programming by breaking the problem down into subproblems. We can solve the problem in two iterations. In the first iteration, we will rob the first house and not the last, while in the second iteration we will rob the last house and not the first. Since the houses are arranged in a circle, these two iterations will account for all possible house robbing scenarios.

Let us assume the amount of money in each house is stored in an array called nums. We will also create two arrays to keep track of the maximum amount of money that can be robbed up to a certain house. These two arrays are:

• dp1[]: This array will store the maximum amount of money that can be robbed up to any house in the first iteration.
• dp2[]: This array will store the maximum amount of money that can be robbed up to any house in the second iteration.

We will use the following recurrence relation to update the values in these two arrays:

dp[i] = max(dp[i-1], dp[i-2]+nums[i])

Here, dp[i] represents the maximum amount of money that can be robbed up to house i, nums[i] represents the amount of money in house i, and max(dp[i-1], dp[i-2]+nums[i]) represents the maximum amount of money that can be robbed up to house i either by not robbing the current house(i.e. robbing only up to house i-1) or by robbing the current house and skipping the previous house (i.e. robbing up to house i-2 and adding the money in house i).

The two iterations will be as follows:

Iteration 1:

For the first iteration, we will update the values in dp1[] in a similar manner as the House Robber problem without a circular arrangement of houses. We will skip the last house and start from the first house.

dp1[0] = nums[0] dp1[1] = max(nums[0], nums[1])
for i in range(2, len(nums)-1):
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
max1 = dp1[-2]

Here, dp1[0] and dp1[1] are initialized based on the same logic as the standard House Robber problem. We are excluding the last house, so we are updating the values only up to len(nums)-1. The maximum amount of money that can be robbed in the first iteration will be stored in max1, which will be dp1[-2] since we are excluding the last house in the first iteration.

Iteration 2:

For the second iteration, we will update the values in dp2[] in a similar manner as the first iteration. However, we will skip the first house and start from the second house. We will also exclude the first house in the maximum amount of money we calculate since it has already been robbed in the first iteration.

dp2[1] = nums[1] dp2[2] = max(nums[1], nums[2])
for i in range(3, len(nums)):
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
max2 = dp2[-1]

Here, dp2[1] and dp2[2] are initialized based on the same logic as the standard House Robber problem. We are excluding the first house and starting from the second house in this iteration. The maximum amount of money that can be robbed in the second iteration will be stored in max2, which will be dp2[-1] since we are including all houses in this iteration.

Finally, the maximum amount of money that can be robbed without alerting the police will be the maximum value of max1 and max2.

max_money = max(max1, max2)

Therefore, the complete solution to the House Robber problem on LeetCode would be:

def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0] if len(nums) == 2:
return max(nums)

dp1 = [0]*len(nums)
dp2 = [0]*len(nums)

# First iteration
dp1[0] = nums[0]
dp1[1] = max(nums[0], nums[1])
for i in range(2, len(nums)-1):
    dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
max1 = dp1[-2]

# Second iteration
dp2[1] = nums[1]
dp2[2] = max(nums[1], nums[2])
for i in range(3, len(nums)):
    dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
max2 = dp2[-1]

max_money = max(max1, max2)

return max_money

Step by Step Implementation For House Robber

/**
 * This is a classic DP problem. We define an array dp[] where each element dp[i] represents the maximum amount of money 
 * that can be robbed if the robber starts from house i. 
 * 
 * We have two cases to consider when we are at some house i:
 * 
 * Case 1: The robber robs the current house i. In this case, we have dp[i] = nums[i] + dp[i - 2] since we cannot rob the 
 * previous house (i - 1) as it will lead to consecutive houses being robbed.
 * 
 * Case 2: The robber does not rob the current house i. In this case, we have dp[i] = dp[i - 1].
 * 
 * Therefore, we can formulate our DP solution as follows:
 * 
 * dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1])
 * 
 * We can further optimize the space complexity of our solution by only using two variables instead of an entire array. 
 * We define two variables prevNo and prevYes where prevNo represents the maximum amount of money that can be robbed if 
 * the robber does not rob the current house and prevYes represents the maximum amount of money that can be robbed if 
 * the robber robs the current house. 
 * 
 * Therefore, we can update our two variables in each iteration as follows:
 * 
 * prevNo = Math.max(prevNo, prevYes)
 * 
 * prevYes = nums[i] + prevNo
 * 
 * At the end, prevNo or prevYes (whichever is larger) represents the maximum amount of money that can be robbed.
 */

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int prevNo = 0;
        int prevYes = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int temp = prevNo;
            prevNo = Math.max(prevNo, prevYes);
            prevYes = nums[i] + temp;
        }
        
        return Math.max(prevNo, prevYes);
    }
}

def rob(self, nums: List[int]) -> int:
        # Base case
        if len(nums) == 0:
            return 0
        
        # First case is when we rob the first house
        # Second case is when we don't rob the first house
        dp = [0] * len(nums)
        dp[0] = nums[0]
        
        for i in range(1, len(nums)):
            # If we rob the current house, we can't rob the previous one
            # So we take the current value plus the value from two houses ago
            if i - 2 >= 0:
                dp[i] = max(dp[i-2] + nums[i], dp[i-1])
            # If we don't rob the current house, we just take the value from the previous house
            else:
                dp[i] = dp[i-1]
                
        # Return the maximum of the two cases
        return max(dp[-1], dp[-2])

//Solution:

//This problem can be solved using dynamic programming. We can keep track of the maximum profit up to the current index in an array and return the last element of the array as the result.

//For each index, we have two options: either rob the current house or not. If we rob the current house, the maximum profit up to the current index will be the value of the current house plus the maximum profit up to the previous index. If we don't rob the current house, the maximum profit up to the current index will be the maximum profit up to the previous index.

//We can keep track of the maximum profit up to the current index in an array and return the last element of the array as the result.

function rob(nums) {
    if (nums.length === 0) return 0;
    
    const dp = [nums[0]];
    
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i] + (dp[i-1] || 0), dp[i-1] || 0);
    }
    
    return dp[nums.length - 1];
}

You can find the problem statement here: https://leetcode.com/problems/house-robber/

class Solution {
public:
    int rob(vector& nums) {
        // Base case
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        
        // Initialize dp array
        // dp[i] represents the maximum amount of money that can be robbed from houses [0, i]
        vector dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        // Fill in dp array
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
        }
        
        // Return the maximum amount of money that can be robbed from all houses
        return dp[nums.size() - 1];
    }
};

public int Rob(int[] nums) {
        int prevNo = 0;
        int prevYes = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            int temp = prevNo;
            prevNo = Math.Max(prevNo, prevYes);
            prevYes = nums[i] + temp;
        }
        return Math.Max(prevNo, prevYes);
    }