213.md

213. House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

my thoughts:

1. reduce the cycle to acyclic.

my solution:

**********
class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # if we rob 0, we cannot rob n-1, this problem becomes acyclically rob 0 to n-2
        # if we rob n-1, we cannot rob 0 --> 1 to n-1
        # if we do not rob 0 or n-1 --> 1 to n-2 --> should be a subset of 0 to n-2
        # so return max(0 to n-2, 1 to n-1)
        def helper(nums, s, e):
            rob, norob = 0, 0
            for i in range(s, e+1):
                temp = nums[i] + norob
                norob = max(rob, norob)
                rob = temp
            return max(rob, norob)
        if not nums: return 0        
        if len(nums)<3: return max(nums)
        return max(helper(nums, 0, len(nums)-2), helper(nums, 1, len(nums)-1))
        

my comments:

from other ppl's solution:

1. N/A