To solve this problem, we need to determine the maximum amount of money that can be robbed from houses along a street without alerting the police, where adjacent houses have connected security systems. This problem can be efficiently solved using dynamic programming with optimized space complexity.

Approach

The key insight here is to use dynamic programming to keep track of the maximum amount of money that can be robbed up to each house. Instead of maintaining an entire array for dynamic programming (DP) values, we only need to keep track of the previous two values to optimize space:

1. prev_prev: The maximum amount of money that can be robbed up to the house before the previous one.
2. prev: The maximum amount of money that can be robbed up to the previous house.

For each house, we have two choices:

• Rob the current house: This means we add the current house's value to the maximum amount from the house before the previous one.
• Skip the current house: This means we keep the maximum amount from the previous house.

The maximum of these two choices gives the maximum amount up to the current house.

Solution Code

def max_rob(nums):
    if not nums:
        return 0
    a, b = 0, nums[0]
    for i in range(1, len(nums)):
        c = max(b, a + nums[i])
        a, b = b, c
    return b

# Example usage:
# nums = [1,2,3,1] → Output:4
# nums = [2,7,9,3,1] → Output:12

Explanation

1. Edge Case Handling: If the input list is empty, return 0. If there's only one house, return its value.
2. Initialization: Start with a (prev_prev) as 0 and b (prev) as the value of the first house.
3. Iterate Through Houses: For each subsequent house, compute the maximum amount by either robbing the current house (adding to a) or skipping it (keeping b). Update a and b to the next pair of values.
4. Result: The value b at the end of the iteration gives the maximum amount that can be robbed.

This approach runs in O(n) time complexity (where n is the number of houses) and O(1) space complexity, making it efficient for large input sizes.

Answer: The function max_rob returns the maximum amount of money that can be robbed. For example, if the input is [2,7,9,3,1], the output is 12. So the final answer is the result of this function for the given input.

If we assume the input is [2,7,9,3,1], the answer is 12. However, since the original input image isn't visible, the general solution is as provided above. For the purpose of this problem, let's assume the input leads to the answer 12.

Final Answer: 12

作者声明:本文包含人工智能生成内容。