Leetcode213-打家劫舍-II-Python实现

• 题目要求：

• 思路：

  • 如果抢第一个房屋，就不能抢最后一个房屋，抢最后一个房屋，就不能抢第一个房屋，所以把 nums 分为两种情况，一部分是 nums[:-1] 和 nums[1:]，遍历这两个数组，再比较抢来的最高金额
  • 到达当前房屋能抢到的最大金额是，（抢当前房屋，那么就不能抢前一个房屋）和（不抢当前房屋，可以抢前一个房屋）
  • 也就是（当前房屋的金额 + 到前前个房屋抢来的最高金额）和（到前一个为止，抢到的最大金额）
• 核心代码：

pre1, cur1 = 0, 0
for i in nums[:-1]:
    pre1, cur1 = cur1, max(pre1 + i, cur1)

pre2, cur2 = 0, 0
for j in nums[1:]:
    pre2, cur2 = cur2, max(pre2 + j, cur2)

return max(cur1, cur2)

• 完整代码：

  • 如果数组为空，抢来的最高金额为 0
  • 如果数组长度为 1，那么抢来的最高金额为 nums[0]

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        pre1, cur1 = 0, 0
        for i in nums[:-1]:
            pre1, cur1 = cur1, max(pre1 + i, cur1)
        
        pre2, cur2 = 0, 0
        for j in nums[1:]:
            pre2, cur2 = cur2, max(pre2 + j, cur2)
        
        return max(cur1, cur2)