详细布置
今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。
198.打家劫舍
视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍_哔哩哔哩_bilibili
代码随想录
class Solution(object):
def rob(self, nums):
if len(nums)==1:
return nums[0]
dp=[0]*len(nums) #代表的是0到i的房屋最高可获得多少的钱
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[len(nums)-1]总结
这道题知道方程式怎么写就应该可以写出来了。背包的题做多了之后还以为dp数组是背包问题才会有的，结果导致动态问题不知道怎么写了。
213.打家劫舍II
视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II_哔哩哔哩_bilibili
代码随想录
思路
对于一个数组，成环的话主要有如下三种情况：
- 情况一：考虑不包含首尾元素
- 情况二：考虑包含首元素，不包含尾元素
- 情况三：考虑包含尾元素，不包含首元素
class Solution(object):
def rob(self, nums):
if len(nums)==1:
return nums[0]
if len(nums)==2:
return max(nums[0],nums[1])
result1=self.robRange(0,len(nums)-2,nums) #包前不包后
result2=self.robRange(1,len(nums)-1,nums) #包后不包前
return max(result1,result2)
def robRange(self,left,right,nums):
#prev_max和curr_max相当于用的是双指针
prev_max = nums[left] #相当于规定dp[0]
curr_max = max(nums[left],nums[left+ 1]) #相当于规定dp[1]
for i in range(left+2,right+1):
temp=curr_max
curr_max=max(curr_max,prev_max+nums[i])
prev_max=temp
return curr_max
总结
这个方法妙鸭。算了，想不到的就不会吧，下次就会了。
337.打家劫舍III
视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3_哔哩哔哩_bilibili
代码随想录
class Solution:
memory = {}
def rob(self,root):
if root is None:
return 0
if root.left is None and root.right is None:
return root.val
if self.memory.get(root) is not None: #相当于dp数组，在memory中添加root且最后返回答案
return self.memory[root]
# 偷父节点
val1 = root.val
if root.left:
val1 += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val1 += self.rob(root.right.left) + self.rob(root.right.right)
# 不偷父节点
val2 = self.rob(root.left) + self.rob(root.right)
self.memory[root] = max(val1, val2)
return max(val1, val2)总结
这真的是中等难度吗，感觉一点思路都没有。开始我是想的是他添加的时候是一排的都会添加，所以用回溯法，结果他不是一排都可以添加，思路理解错了。答案用的是定义，dp数组是0到root所能得到的最大值，val1表示偷当前节点，val2表示不偷当前节点。
