198. 打家劫舍
213. 打家劫舍 II
337. 打家劫舍 III
198. 打家劫舍
动态规划
- 设有n个房子，那前n个房子能偷到的最大金额为
dp[n] - 现在我们添加一个房间作为辅助，现在有
n+1个房子，因为条件限制不能偷相邻的房间，所以在偷到最后一间房时的最高金额要么是dp[n]，要么是dp[n-1] + num，我们要做的是在这两个方案中取最大值即可。 - 转移方程为：
dp[n+1] = max(dp[n], dp[n-1] + num)，简化后变成dp[n] = max(dp[n-1], dp[n-2] + num) - 最后将
dp[n-1]和dp[n-2]替换为cur和pre来优化空间复杂度为O(1)
代码
class Solution:
def rob(self, nums: List[int]) -> int:
pre, cur = 0, 0
for n in nums:
cur, pre = max(cur, pre + n), cur
return cur
213. 打家劫舍 II
该题在198. 打家劫舍的基础上增加了房屋围成一圈的限制，此时我们只需要考虑这个条件即可。
仔细想想可以知道，相比于上题不能偷连续的房屋，但起码第一个房屋和最后一个房屋没有任何关系，本题直接将第一个房屋与最后一个房屋也加上了限制。
- 同样的思路，因为不能同时偷第一个房屋和最后一个房屋，所以将这两种情况分开进行对比，返回最大值即可。用切片将两种情况分为
nums[:-1]和nums[1:]。 - 如果只有一个房屋就不考虑该情况
代码
class Solution:
def rob(self, nums: List[int]) -> int:
def helper(nums):
pre, cur = 0, 0
for n in nums:
pre, cur = cur, max(cur, pre+n)
return cur
return max(helper(nums[:-1]), helper(nums[1:])) if len(nums) != 1 else nums[0]