Daily Problem: LC 213 House Robber II

213. House Robber II

Jimmy (xiaoke) Shen

·

Follow

1 min read

·

Oct 14, 2020

--

Listen

Share

Solution with comments in python3

class Solution:
    def house_rob(self, nums):
        if not nums:return 0
        if len(nums) <=2:return max(nums)
        rob, not_rob = 0, 0
        ret = 0
        for num in nums:
            # not rob at this num will be: max( rob + 0, not_rob)
            # 0 means not rob at this num
            new_not_rob = max(rob, not_rob)
            # new_rob will be old not rob + num
            new_rob = not_rob + num
            rob, not_rob = new_rob, new_not_rob
            ret = max(ret, not_rob, rob )
        return ret    def rob(self, nums: List[int]) -> int:
        if len(nums) <=2: return max(nums)
        # we can not rob the first and the last at the same time. So the 
        # problem is change to either rob the 0 to n-2 inclusively 
        # or 1 to n-1 inclusively. 
        return max(self.house_rob(nums[:-1]), self.house_rob(nums[1:]))