leetcode 198 打家劫舍

使用动态规划，看第几间屋子是偷还是不偷，偷的话由之前的没偷的状态转移过来，不偷的话之前可能偷了也可能没偷。

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp=[[0,0] for _ in range(len(nums))]
        dp[0][0]=0
        dp[0][1]=nums[0]
        for i in range(1,len(nums)):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1])
            dp[i][1]=dp[i-1][0]+nums[i]
        return max(dp[len(nums)-1][1],dp[len(nums)-1][0])

空间优化，注意需要同步更新当前家的偷和没偷值，所以要先设定一个变量。

class Solution:
    def rob(self, nums: List[int]) -> int:

        norob=0
        rob=nums[0]
        for i in range(1,len(nums)):
            temp1=max(rob,norob)
            temp2=norob+nums[i]
            norob=temp1
            rob=temp2
        return max(norob,rob)

将状态看成前k个家庭的最大金额，来进行状态转移，要么是前k-1家的，要么是k-2家，然后偷了当前的。

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

        return dp[len(nums)-1]