[LeetCode] 213. House Robber II

 Problem : https://leetcode.com/problems/house-robber-ii/

Since the first and the last house are exclusive to each other. 

We can break it into 2 cases:

- Start from the first house and end at the 2nd from the last house.

- Start from the 2nd house and end at the last house.

The answer is the max value of the 2 cases.

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        @lru_cache(maxsize = None)
        def helper(i, end, safe):
            """
            i : current house
            end: last house index
            safe: safe to rob
            """
            if i == end:
                return 0
            
            stolen = 0
            
            if safe:
                stolen = max(nums[i] + helper(i+1, end, False), helper(i+1, end, True))
            else:
                stolen = helper(i+1, end, True)
            
            return stolen
        
        if not nums:
            return 0
        
        if len(nums) < 2:
            return max(nums)
        
        return max(helper(0, len(nums) - 1, True), helper(1, len(nums), True))

Bottom-Up approach

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        def helper(houses):
            steal = [0] * len(houses)
            steal[0] = houses[0]
            
            notSteal = [0] * len(houses)
            
            for i in range(1, len(houses)):
                steal[i] = notSteal[i-1] + houses[i]
                notSteal[i] = max(notSteal[i-1], steal[i-1])
          
            return max(steal[-1], notSteal[-1])
        
        if not nums:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        if len(nums) == 2:
            return max(nums[0], nums[1])
        
        return max(helper(nums[1:]), helper(nums[:-1]))