打家劫舍II

问题简述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

213. 打家劫舍 II - 力扣（LeetCode）

思路

• 与打家劫舍的唯一区别就是不能同时偷首尾两家；

• 因此可以考虑分别计算 nums[1:] 和 nums[:-1]，求较大值；

  打家劫舍 II（动态规划，结构化思路，清晰题解） - Krahets

Python

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

        def f(nums):
            N = len(nums)
            dp = [0] * (N + 1)
            dp[1] = nums[0]

            for i in range(2, N + 1):
                dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
            
            return dp[-1]
        
        return max(f(nums[1:]), f(nums[:-1]))