代码随想录-Day-44-第九章-动态规划part-07198.打家劫舍213.打家劫舍II337.打家劫舍III
代码随想录 Day 44 | 【第九章 动态规划part 07】198.打家劫舍、213.打家劫舍II、337.打家劫舍III
一、198.打家劫舍
198.打家劫舍
视频讲解：
1. 解题思路
（1）dp数组的含义：考虑下标i（包含下标i及之前的房间）所能偷的最大的金币为dp[i]。求dp[len(nums)-1]， 仅仅是考虑范围，而不是一定偷或不偷 。
（2）递推公式：两种状态偷/不偷，偷第i个房间（dp[i-2]+dp[i]），不偷（dp[i-1]），所以递推公式为dp[i] = max(dp[i-2]+dp[i], dp[i-1])。
（3）dp数组初始化：dp[0] 表示一个房间，那么肯定偷，所以dp[0] = nums[0]；dp[1]表示有两个房间，选一个偷，所以取最大值，dp[1] = max(nums[0], nums[1])；非0/1下标初始化为默认0，反正后续都会被覆盖。
（4）遍历顺序：从小到大遍历，i才能用到两个状态，i从2开始，因为0和1已经初始化。
（5）打印dp数组。
2. 代码实现
class Solution:
def rob(self, nums: List[int]) -> int:
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(nums[i]+dp[i-2], dp[i-1])
return dp[-1]二、213.打家劫舍II
213.打家劫舍II
视频讲解：
1. 解题思路
（1）相比于打家劫舍I，多了形成环的条件，一共有一下三种情况，情况二和情况三包含了情况一的最优解，特别注意是考虑而不是一定是真的需要偷。
（2）由于情况二、三包含了情况一的最优解，所以只需要将情况二、三的线性数组传入打家劫舍Ⅰ的函数，最后取最大值即可，由此将环形问题转化为线性问题。
2. 代码实现
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
res1 = nums[:len(nums)-1]
res2 = nums[1:]
res = max(self.robIndex(res1), self.robIndex(res2))
return res
def robIndex(self, nums: List[int]) -> int:
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-1], dp[i-2]+nums[i])
return dp[-1]三、337.打家劫舍III
337.打家劫舍III
视频讲解：
1. 解题思路
本题的房间是树形dp。
（1）dp数组的定义：每个节点只有两个状态（偷/不偷），定义长度为2的dp数组，dp[0]为不偷、dp[1]为偷，每一层递归都有自己的当前状态的dp数组。dp[0]表示不偷当前节点所获得的最大金钱，dp[1]表示偷当前节点所获的最大金钱。这个二叉树需要从底向上去遍历，也就是后序遍历，最终结果是根节点偷与不偷的最大值。
（2）递归函数三部曲：1）确定递归函数的参数和返回值：返回值是一维的长度为2的dp数组（当前节点的偷与不偷的状态的最大值），传入参数是根节点。2）递归函数的终止条件：如果当前遍历的值为null，那么返回均初始为0的数组（长度为2）。3）遍历顺序：定义一个偷当前节点的变量，得到cur.value，不偷左右孩子的最大钱币是int val1 = cur.val+leftdp[0]+rightdp[0]。
（3）遍历顺序：后序遍历为左右中，分别得到左右孩子偷与不偷得到的最大值，所以计算当前节点偷与不偷的最大值，偷当前节点的最大值为int val1 = cur.val+leftdp[0]+rightdp[0]。如果不偷当前节点，那么就要考虑是否偷左右孩子，需要考虑偷与不偷的最大值，int val2 = max(leftdp[0], rightdp[1])+max(rightdp[0], rightdp[1])。
（4）打印dp数组。
2. 代码实现
# 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:
dp = self.traversal(root)
return max(dp)
def traversal(self, node):
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
val_1 = max(left[0], left[1]) + max(right[0], right[1])
val_2 = node.val + left[0] + right[0]
return (val_1, val_2)