那些网站做调查能赚钱,建设银行博士后招聘网站,免费做淘宝客网站有哪些,在国税网站更换购票员怎么做198.打家劫舍
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个…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] 213.打家劫舍II 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 解题思路 本题与上一题区别在于环形数组和直线数组环形数组首尾不能同时取值因此分为三种情况 不考虑首尾的数组不考虑尾部的数组不考虑首部的数组 可以发现2 3包含情况一因此只需要在23中取最大值即可。 dp五步骤 确定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]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:])) 337.打家劫舍III 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。 除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 示例 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, val0, leftNone, rightNone):
# 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))
