House Robber II

Question

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.

Question Analysis

与1不同的只是，第一个和最后一个现在算相邻了，不能都包括

Thoughts

所以有两种情况

• 包含第一个，不包含最后一个
• 不包含第一个，包含最后一个

用I的做法分别遍历两遍A[:length-1], A[1:]

Solution

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0 
        length = len(nums)
        if length < 3:
            return max(nums)
        result1 = self.houseRobber1(nums[:length-1])
        result2 = self.houseRobber1(nums[1:])
        return max(result1, result2)

    def houseRobber1(self, A):
        # write your code here
        if not A:
            return 0 
        length = len(A)
        if length < 3:
            return max(A)
        dp = [0 for i in range(length)]
        dp[0] = A[0]
        if A[1] > A[0]:
            dp[1] = A[1]
        else:
            dp[1] = A[0]
        for index in range(2, length):
            dp[index] = dp[index-2] + A[index]
            if dp[index-1] > dp[index]:
                dp[index] = dp[index-1]

        return dp[length-1]