198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
# 旁边的最大值和如果偷当前，两个判断
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
213.打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) < 3:
return max(nums)
# 本质上还是第一版，但是第二版抢劫只有四种可能
# 抢第一家，不抢最后一家
# 不抢第一家，抢最后一家
# 不抢第一家，不抢最后一家
# 抢第一家，抢最后一家（这种情况明显不符合题意）
# 因此只需要分开求不抢某一家的最大值，返回最大值就可以了
no_first = self.rob_circle(nums[1:])
no_end = self.rob_circle(nums[:-1])
return max(no_first, no_end)
def rob_circle(self, nums):
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
flag = 0
if nums[0] < nums[1]:
flag = 1
for i in range(2, len(nums)):
if i == len(nums) - 1 and flag == 1:
dp[i] = dp[i - 2] + nums[i]
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
337.打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
res = self.traversal(root)
return max(res)
def traversal(self, node):
if not node:
return (0, 0)
# 左代表已经被偷，不可以偷当前结点
# 右代表还没被偷，可以偷当前结点
left = self.traversal(node.left)
right = self.traversal(node.right)
rob_val = max(left[0], left[1]) + max(right[0], right[1]) # 子结点已经被偷，当前结点不能偷了
no_rob_val = node.val + left[1] + right[1] # 子结点没被偷过，这个结点可以偷了
return (no_rob_val, rob_val)