House Robber II
You are a professional thief planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Examples:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob the first and the last house at the same time, so you can rob the first house and get 2, or rob the last house and get 2, or rob the middle house and get 3. The maximum amount of money you can rob is 3.
Solutions
Dynamic Programming
We use two dynamic programming arrays, dp1 and dp2, to keep track of the maximum amount of money we can rob up to each house, considering the first and last houses separately. We then return the maximum of the two arrays at the end.
def rob(nums):
n = len(nums); dp1, dp2 = [0]*n, [0]*n; dp1[0], dp2[0] = nums[0], nums[0]; for i in range(1, n):
dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]) if i < n-1 else dp1[i-1]; dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i]) if i > 0 else dp2[i-1]; return max(dp1[-2], dp2[-1])Follow-up:
House Robber III
