213. House Robber II
213. House Robber II
这道题是对198的简单扩展
Leetcode打家劫舍系列的对比可以参考Leetcode198. House Robber
题目
思路
由于是环状,且相邻房屋不能同时被劫,只要保证第一个房屋和最后一个房屋不会同时被劫即可,将第一个房屋排除,对[1,n]的房屋进行一次Leetcode198. House Robber的操作,
将最后一个房屋排除,对[0,n-1]的房屋也进行一次同样的处理
将两个取最大即可
复杂度
-
时间复杂度 O ( n ) \mathcal{O}(n) O(n)
两次从前到后遍历,都是 O ( n ) \mathcal{O}(n) O(n) -
空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
同Leetcode198. House Robber的分析
代码
class Solution:
def rob(self, nums) -> int:
if len(nums) <= 3:
return max(nums)
# 头尾必有一个不能抢,去掉分别进行dp
max1 = max2 = 0
a1, b1 = nums[0], max(nums[0], nums[1])
a2, b2 = nums[1], max(nums[1], nums[2])
for i in range(2, len(nums) - 1):
max1 = max(b1, a1 + nums[i])
a1 = b1
b1 = max1
for i in range(3, len(nums)):
max2 = max(b2, a2 + nums[i])
a2 = b2
b2 = max2
return max(max1, max2)