[Algorithm] 213-house-robber2

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

House Robber II - LeetCode

 

1. 시간복잡도 - O(n) : 똑같은 알고리즘(helper function) 2번 호출할 뿐임

2. 공간복잡도 - O(1) : don't need any extra data structure. just 변수 2개만 사용하고 있음.

class Solution(object):
    def rob(self, nums):
        return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1]))

    def helper(self, nums):
        rob1, rob2 = 0, 0
        for n in nums:
            newRob = max(rob1 + n, rob2)
            rob1 = rob2
            rob2 = newRob
        return rob2