House Robber Problem

Lecture 101:-  House Robber Problem

The House Robber problem is a classic dynamic programming problem. In this problem, you are given an array representing the wealth in each house on a street. The goal is to find the maximum amount of money you can rob without robbing adjacent houses, as robbing two adjacent houses will trigger an alarm.

Here's a Python function that solves the House Robber problem using dynamic programming:

pythonCopy code

def house_robber(nums):    if not nums:        return 0    n = len(nums)    if n == 1:        return nums[0]    # Create a dp array to store the maximum amount of money that can be robbed up to the current house    dp = [0] * n    dp[0] = nums[0]    dp[1] = max(nums[0], nums[1])    for i in range(2, n):        # The maximum amount of money that can be robbed at the current house is the maximum of:        # 1. The maximum amount of money robbed up to the previous house (dp[i-1])        # 2. The current house's wealth plus the maximum amount of money robbed up to two houses ago (dp[i-2])        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])    return dp[-1] # Test the function house_wealth = [1, 2, 3, 1] print(house_robber(house_wealth))  # Output: 4 (Rob the first and the third house) house_wealth = [2, 7, 9, 3, 1] print(house_robber(house_wealth))  # Output: 12 (Rob the second and the fourth house)

In this code, the house_robber() function takes an array nums representing the wealth in each house. It creates a dp array to store the maximum amount of money that can be robbed up to the current house. The dynamic programming approach iterates through the houses, and at each step, it calculates the maximum amount of money that can be robbed at the current house based on the previous results stored in the dp array.

The final result will be the maximum amount of money that can be robbed without robbing adjacent houses. The time complexity of this solution is O(n), where n is the number of houses.