To solve this problem, we need to determine the maximum amount of money that can be robbed from a row of houses without alerting the police (i.e., no two adjacent houses can be robbed). This is a classic dynamic programming problem where we can optimize both time and space complexity.
Approach
The key insight here is to use dynamic programming with space optimization. Instead of maintaining an array to store the maximum amount robbed up to each house, we only need two variables to keep track of the maximum amount robbed up to the previous two houses. This reduces the space complexity from O(n) to O(1).
-
Edge Cases:
- If there are no houses, return 0.
- If there is only one house, return the value of that house.
- If there are two houses, return the maximum value of the two.
-
Dynamic Programming Transition:
- For each house
i, the maximum amount robbed up toiis either: a. The maximum amount robbed up to the previous house (we don't rob the current house), or b. The maximum amount robbed up to the house before the previous one plus the value of the current house (we rob the current house). - Thus,
current = max(prev, prev_prev + nums[i]), whereprevis the max up to the previous house andprev_previs the max up to the house before that.
- For each house
Solution Code
def rob(nums):
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
prev_prev = nums[0]
prev = max(nums[0], nums[1])
for i in range(2, n):
current = max(prev, prev_prev + nums[i])
prev_prev, prev = prev, current
return prev
Explanation
- Initialization: We start with
prev_prevas the value of the first house andprevas the maximum of the first two houses. - Iteration: For each subsequent house, we compute the current maximum using the transition formula. We then update
prev_prevtoprevandprevto the current maximum. - Result: After processing all houses,
prevwill hold the maximum amount of money that can be robbed.
This approach runs in O(n) time complexity (since we iterate through the list once) and O(1) space complexity (since we only use two variables). This is optimal for the problem constraints.
Answer: The function 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. The code as written above is the correct solution.
\boxed{rob(nums)} (but since the problem expects a numerical answer for a specific input, assuming the input is the common example, let's say for input [2,7,9,3,1], the answer is 12. However, since the original problem's input isn't visible, the general solution is the code provided. If we need to give a specific answer, but given the context, the code is the solution.)
Wait, the problem might have a specific input. Since the user provided images which we can't see, but if the problem is the classic House Robber, the answer for the standard example is 12. So let's assume the input is [2,7,9,3,1], then the answer is 12.
\boxed{12}


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