213.打家劫舍II.md

213. 打家劫舍 II

https://leetcode-cn.com/problems/house-robber-ii/

一：dp

比198打家劫舍多了头尾连起来的约束，可以用整体法，数组分为头+中间+尾，将头尾分离出来考虑，可以发现这些约束对中间部分是无影响的。 由于此处限制头尾不能同时取，因此 原问题转化为，求【头+中间】和【尾+中间】的较大者，之前的算法可以复用

class Solution:
    def rob(self, nums) -> int:
    	#198打家劫舍原方法
        def help(nums):
            n = len(nums)
            if n == 1:
                return nums[0]
            dp = [0] * n
            dp[0] = nums[0]
            dp[1] = max(dp[0], nums[1])
            if n == 2:
                return dp[1]
            for i in range(2, n):
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
            return dp[n - 1]
        #边界情况
        if len(nums) == 1:
            return nums[0]
        #求去尾和去头的较大者
        return max(help(nums[:-1]), help(nums[1:]))