有限公司网站建设 互成网络地址 四川太原专门做网站

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解题思路：

确定dp数组含义：dp[i]遍历到房屋index为i时所能打劫到的最多钱

确认递推公式：dp[i]取决于前一个房屋和前两个房屋是否有被偷，如果前一个被偷，则不能偷第i个，如果第i-2个被偷，可选择是否偷第i个。dp[i] = max(dp[i-2]+nums[i], dp[i-1])

初始化：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

遍历顺序：从小到大遍历

打印dp数组

class Solution:def rob(self, nums: List[int]) -> int: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]

class Solution:def rob(self, nums: List[int]) -> int:if len(nums)<=1:return nums[0]def helper(subnums):if len(subnums)<=1:return subnums[0]dp = [0]*len(subnums)dp[0] = subnums[0]dp[1] = max(subnums[0], subnums[1])for i in range(2, len(subnums)):dp[i] = max(dp[i-2]+subnums[i], dp[i-1])print(dp)return dp[len(subnums)-1]return max(helper(nums[:-1]), helper(nums[1:]))

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

解题思路：

本体使用递归三部曲结合dp五步骤，设置dp[0],dp[1]表示打劫当前节点和不打劫当前节点的最大值，每个node有一组对应的dp[0], dp[1]。使用后序遍历，当前节点dp值需要结合其左右节点dp进行分析。 递归三步骤：确定递归参数，确定停止条件，递归逻辑。输入参数统一为当前节点即表示为root， 当root == null停止并返回0，再遍历左右子树，中间值取最大dp值。

重点理解

val1 = root.val + leftdp[0] + rightdp[0]#行窃root

val2 = max(leftdp[0],leftdp[1])+max(rightdp[0], rightdp[1])#不行窃root，选取左右子树行窃或不行窃时的最大值，两边取max。

代码如下：

# 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 helper(root):if not root:return [0,0]leftdp = helper(root.left)rightdp = helper(root.right)val1 = root.val + leftdp[0] + rightdp[0]#行窃rootval2 = max(leftdp[0],leftdp[1])+max(rightdp[0], rightdp[1])#不行窃rootreturn [val2, val1]return max(helper(root))