LeetCode 213. 打家劫舍 II

题目

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

例：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

方法：动态规划

思路类似 198. 打家劫舍，区别在于该题房屋是围成一圈的，即首尾房屋无法同时被偷窃，所以需分两种情况：考虑偷窃第一个房屋和考虑偷窃最后一个房屋
※ 考虑并非一定偷窃
rob 函数：

• 若数组 nums 长度为 1，即只有一个房屋，那么最高偷窃金额为该房屋的金额
• 若数组 nums 长度为大于等于 2，即有两个或两个以上房屋，那么分别计算考虑偷窃第一个房屋和考虑偷窃第二个房屋的最高金额，两者之中的最大值即为所求的偷窃最高金额

robRange 函数：

• dp[i] 表示下标 i 和 i 以内的房屋，最高偷窃金额
• 由 rob 函数部分我们可知原数组此时至少长度为 2，那么在去掉首或尾房屋后，现数组的长度至少为 1。初始化 dp[0]，即此时的第一个房屋的金额为 nums[0]
  ※ 因为此时数组 nums 的长度为大于等于 1，所以并不能像 198. 打家劫舍 一样将 dp[1] 直接定义
• 从前向后进行遍历，若下标为 1，即第二间房屋，那么此时的最高偷窃金额为第一个房屋 nums[0] 和第二个房屋 nums[1] 的最大值；
• 否则，若偷下标为 i 的房屋，那么最高偷窃金额为 dp[i-2] + nums[i]；若不偷下标为 i 的房屋，那么最高偷窃金额为 dp[i-1]，取该两个的最大值

class Solution(object):
    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        val1 = self.robRange(nums[:-1])
        val2 = self.robRange(nums[1:])
        return max(val1, val2)
    
    def robRange(self, nums):
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            if i == 1:
                dp[1] = max(nums[0], nums[1])
            else:
                dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[-1]

参考

代码相关：https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html