213 House Robber2

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

思路：跟上题大致相同，重点是怎么把环形拆成array来做，其实，array[0:n-1]和array[1:n]的dp结果最大的就是最优解。 可以理解为最优解要么包含这个房子，要么不包含这个房子。包含这个房子时，肯定不包含相邻的房子。所以直接从array里面删掉2个相邻的，拆成array来解两次，得到最优就行了。

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

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        # if house smaller than 2.
        if len(nums)<=3:
            return max(nums)

        # do rob from nums[1:n]
        dp = [0]+[nums[1]]

        # do the dp loop
        for i in range(2, len(nums)):
            dp.append(max(dp[-2]+nums[i], dp[-1]))
        res1 = dp[-1]

        # do rob from nums[0:n-1]
        dp = [0]+[nums[0]]

        # do the dp loop
        for i in range(1, len(nums)-1):
            dp.append(max(dp[-2]+nums[i], dp[-1]))
        res2 = dp[-1]

        return max(res1, res2)

so = Solution()
print so.rob([2,3,5,2,1])