代码随想录算法训练营第四十八天| 198. 打家劫舍，213. 打家劫舍 II，337. 打家劫舍 III
198. 打家劫舍
题目链接：打家劫舍
这里注意一下：
dp[i-2]是nums[:(i-1)]间房偷到最大的，并不一定是偷了nums[i-2]的家，如果nums[i-3]更大那家也行。
class Solution:
def rob(self, nums: List[int]) -> int:
# dp[i] = nums[:(i+1)]间房能偷到的最大金额
dp = [0]*(len(nums)+1)
dp[1] = nums[0]
for i in range(2,len(nums)+1):
#不偷这家，dp[i-1]
#偷这家，dp[i-2]+nums[i-1]
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[-1]
213. 打家劫舍 II
题目链接：打家劫舍 II
nums = [1,2,3,1,4]
因为是一个圈，所以偷1就不偷4，偷4就不偷1，那么就设立两个list，一个有1无4，一个有4无1，然后取最大值就好了。
class Solution:
def rob(self, nums: List[int]) -> int:
#dp[i] = nums[:(i+1)]间房能偷到的最大金额
if len(nums) == 1: return nums[0]
nums1 = nums[:(len(nums)-1)]
nums2 = nums[1:]
dp1 = [0]*len(nums)
dp2 = [0]*len(nums)
dp1[1] = nums1[0]
dp2[1] = nums2[0]
for i in range(2,len(nums)):
dp1[i] = max(dp1[i-1],dp1[i-2]+nums1[i-1])
dp2[i] = max(dp2[i-1],dp2[i-2]+nums2[i-1])
return max(dp1[-1],dp2[-1])
337. 打家劫舍 III
题目链接：打家劫舍 III
暴力解法
跑到122 / 124，超时了，思路应该没错，但是暴力解法。
如果偷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:
if not root:
return 0
if (not root.left) and (not root.right):
return root.val
dp = root.val
if root.left:
dp += self.rob(root.left.right)+self.rob(root.left.left)
if root.right:
dp += self.rob(root.right.right)+self.rob(root.right.left)
dp = max(dp,self.rob(root.left)+self.rob(root.right))
return dp
解决办法是把结果都记录下来，就不用每次走一遍。
class Solution:
memory = {}
def rob(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if (not root.left) and (not root.right):
return root.val
#if self.memory[root] is not None:
#return self.memory[root]
if root in self.memory:
return self.memory[root]
dp = root.val
if root.left:
dp += self.rob(root.left.right)+self.rob(root.left.left)
if root.right:
dp += self.rob(root.right.right)+self.rob(root.right.left)
dp1 = self.rob(root.left)+self.rob(root.right)
self.memory[root] = max(dp,dp1)
return max(dp,dp1)
动态规划
首先要确定一下每个节点的状态，偷还是没偷。
所以我们的dp可以设为二维的。
dp[0] = 没偷
dp[1] = 偷了
每层递归（遍历）都有一个dp数组，进入下一层会更新。
为什么是后序 ，主要是因为最后一个遍历要回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:
def traversal(root):
if not root:
return (0,0)
left = traversal(root.left)
right = traversal(root.right)
#dp0 = left[1] + right[1]
dp0 = max(left[0],left[1]) + max(right[0],right[1])
dp1 = root.val + left[0] + right[0]
return (dp0,dp1)
dp = traversal(root)
return max(dp[0],dp[1])