代码随想录算法训练营第四十四天| 动态规划07
198.打家劫舍
视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍_哔哩哔哩_bilibili
代码随想录
确定递推公式很重要，在递推公式的提示下可以写出该题
dp[i]表示截至第i个房间偷到的最大金额
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==1:
return nums[0]
if len(nums)==1:
return max(nums[0],nums[1])
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-2]+nums[i],dp[i-1])
return dp[len(nums)-1]213.打家劫舍II
视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II_哔哩哔哩_bilibili
代码随想录
在上一题的基础上修改，考虑两种情况，去头或去尾，两种情况返回最大选项
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==1:
return nums[0]
def rob_sub(nums):
if len(nums)==0:
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-2]+nums[i],dp[i-1])
return dp[len(nums)-1]
case1=rob_sub(nums[:-1])
case2=rob_sub(nums[1:])
return max(case1,case2)337.打家劫舍III
视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3_哔哩哔哩_bilibili
代码随想录
dp数组（dp table）以及下标的含义：
1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
# 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 dfs(node):
if not node:
return (0,0)
left=dfs(node.left)
right=dfs(node.right)
not_rob=max(left)+max(right)
rob=node.val+left[0]+right[0]
return (not_rob,rob)
dp=dfs(root)
return max(dp)