House Robber

严格上讲可能是序列型，但是因为当前房子抢与不抢的决策问题，感觉有点类似博弈类

普通版

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [0] * (n + 1)

        for i in xrange(1, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])

        return dp[n]

空间优化版

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        if n < 2:
            return 0 if n == 0 else nums[0]

        dp = [0] * 2
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in xrange(2, n):
            dp[i % 2] = max(dp[i % 2] + nums[i], dp[(i + 1) % 2])

        return dp[(n - 1) % 2]

House Robber II

目前知道的就是把环拆掉两次DP求解最大值，不知道还有没有其他方法

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n <= 1:
            return 0 if n == 0 else nums[0]

        left = [0] * n
        left[1] = nums[0]

        for i in xrange(2, n):
            left[i] = max(left[i - 1], left[i - 2] + nums[i - 1])

        right = [0] * n
        right[1] = nums[1]
        for i in xrange(2, n):
            right[i] = max(right[i - 1], right[i - 2] + nums[i])

        return max(left[-1], right[-1])