213. House Robber II

# time O(N) space O(1)
"""
main idea: choose 1st element means last one can not be choosen. not chooen 1st element means last element can be an option to choose( not determined)=> valid loop range will be correspondinglly [0,len(nums)-1] and [1,len(nums)-2].since loop range differs, we need to discuss in two loops.
Hence we create a general loop body for getting maximum from current choices within valid ranges.

step1: edge case: len(nums) = 0 |len(nums) = 1
step2: two cases => 1. choose 1st element 2. not choose 1st elemenet
    2.1: given start, end point, loop through nums, record previous rob actions and based on previous actions to get current most optimal gains
    2.2 update previous actions by assigning current optimal to previous record since next loop current action will be recaculated.
step3: compare max gains from two cases above, get final max
"""
# time O(N) space O(1)
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:return 0
        if len(nums) == 1: return nums[0]
        exclude_1 = self.helper(nums,1,len(nums)-1)
        include_1 = self.helper(nums,0,len(nums)-2)
        return max(exclude_1,include_1)
    def helper(self,arr,s,e):
        #step1: create middle cache for pre actions' best result so far 
        pre_rob, pre_not_rob = 0,0
        for i in range(s,e+1):
            # step2 based on previous action to get current best results ,given rob or not_rob cases 
            rob, not_rob = pre_not_rob+arr[i] , max(pre_rob,pre_not_rob)
            # step3: update previous best actions, move forward 
            pre_rob,pre_not_rob = rob,not_rob
        return max(rob,not_rob)

class Solution(object):
    def rob(self, nums):
    # time O(N) space O(N)
        res = 0
          # case1: rop 1st one
        size = len(nums)
        if not nums:
            return 0
        if  size ==1:
            return  nums[0]
        memo1 = [0] * size
        memo2 = [0] * size
        #case: use 1st one  
        for i in range(0,size-1):
            memo1[i] = max(nums[(i-1+size)%size] + memo1[(i-2+size)%size],memo1[(i-1+size)%size])
        # case: skip 1st one 
        for i in range(1,size):
            memo2[i] = max(nums[(i-1+size)%size] + memo2[(i-2+size)%size],memo2[(i-1+size)%size])
        return max(max(memo1),max(memo2))

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
          # case1: rop 1st one
        size = len(nums)
        if not nums:
            return 0
        if  size ==1:
            return  nums[0]
        memo1 = [0] * (size+1)
        memo2 = [0] * (size+1)
        # preprocess
        memo1[0] = 0
        memo1[1] = nums[0]
        for i in range(2,size+1):
            # case1: not skip 1st one 
            memo1[i] = max(nums[i-1] + memo1[(i-2)],memo1[i-1])
            # case2: skip 1st one 
            memo2[i] = max(nums[i-1] + memo2[(i-2)],memo2[i-1])
        print(memo1,memo2)
               # cannot get last one    can get last on 
        return max(memo1[size-1],memo2[size])