leetcode213 打家劫舍2

问题将数组改为循环数组，也就是头和尾不能一起偷盗，所以就进行两次计算，一次将数组去除头元素，一次将数组去掉尾元素。

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

            dp[0]=nums[0]           
            for i in range(1,len(nums)):
                if i>=2:
                    dp[i]=max(dp[i-1],dp[i-2]+nums[i])
                else:
                    dp[i]=max(dp[i-1],nums[i])

            return dp[len(nums)-1]

        return max(calu(nums[1:]),calu(nums[:-1]))  

空间优化，类似斐波那契数列的做法。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return nums[0]
        if len(nums)==2:
            return max(nums[0],nums[1])

        def calu(nums):


            a=nums[0]
            b=max(nums[0],nums[1])         
            for i in range(2,len(nums)):
                a,b=b,max(b,a+nums[i])

            return b

        return max(calu(nums[1:]),calu(nums[:-1]))  

通过判断每一家偷还是不偷的状态，详情见打家劫舍1

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

        def calu(nums):
            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][0],dp[len(nums)-1][1])
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return nums[0]
        return max(calu(nums[1:]),calu(nums[:-1]))