198 House Robber

最简单动态规划

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

        dp = []
        dp.append(nums[0])
        if nums[1] > nums[0]:
            dp.append(nums[1])
        else:
            dp.append(nums[0])
        for i in range(2,length):
            p = nums[i]
            if p + dp[i-2] > dp[i-1]:
                dp.append(p + dp[i-2])
            else:
                dp.append(dp[i-1])
        return dp[-1]