House Robber - Leetcode Solution

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

1