Leetcode: House robber II
Similar to “House Robber”, but now we have to assume that the houses are aligned in a circle and the last house is a neighbor of the first house.
We can solve it similarly but remove the first and last element and take the maximum of the result.
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) < 2:
return nums[0]
return max(self.r(nums[:-1]), self.r(nums[1:]))
def r(self, nums):
print(nums)
if len(nums) < 2:
return nums[0]
if len(nums) < 3:
return max(nums[0], nums[1])
m = [0 for _ in nums]
m[0] = nums[0]
m[1] = nums[1]
m[2] = max(m[0]+nums[2], m[1])
for pos in range(3, len(nums)):
m[pos] = max(m[pos-2], m[pos-3]) + nums[pos]
return max(m[-1], m[-2])
Runtime: 63 ms, faster than 22.78% of Python3 online submissions for House Robber II. Memory Usage: 13.9 MB, less than 70.83% of Python3 online submissions for House Robber II.