【Leetcode】198. House Robber

抢劫相邻两个就会触动警报，求最多抢多少钱。

方法1 DP法

假设dp[i]为经过编号为i的房子最多抢的钱，注意这里是经过，第i个房子可抢可不抢。
那么dp[i] = max(dp[i-1], dp[i-2]+nums[i])，前者表示不抢该房子（至于第i-1个房子抢或不抢，不用关心，只要经过i-1的时候利益最大化就行了），后者表示抢该房子。所以dp[i]就表示抢或不抢该房子能获得最大钱数。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
        dp = [0 for i in range(len(nums))]
        for i in range(len(nums)):
            if i == 0:
                dp[i] = nums[i]
            else:
                dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

双变量 DP

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
         #前天昨天=>昨天今天
        money2,money1 = 0,0
        for num in nums:
            money2,money1 = money1, max(money2 + num, money1)
        return money1    

方法2 递归

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
        return self.helper(len(nums)-1, nums)
        
        
    def helper(self, day, nums):
    # -1用来特殊处理前两个元素
        if day == -1:
            return 0
        if day == 0:
            return nums[0]
        else:
            return max(self.helper(day -2, nums) + nums[day], self.helper(day-1, nums))

上述方法存在大量重复计算，会TLE，用dict改进

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
        self.dict = {-1:0, 0:nums[0]}
        return self.helper(len(nums)-1, nums)
        
    def helper(self, day, nums):
        if day in self.dict :
            return self.dict[day]
        else:
            self.dict[day] = max(self.helper(day-2, nums) + nums[day], self.helper(day-1, nums))
            return self.dict[day]