网站建设对于企业的必要性,专业做网站的顺德公司,网站可以做动态背景吗,网站链接到邮箱怎么做198. 打家劫舍
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个…198. 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
思路状态转换机经典题目 dp[i][0]表示第i个房间不偷的最高金额dp[i]表示第i个房屋偷的最高金额状态转移方程为 dp[i][0] max(dp[i-1][1] dp[i-1][0]), dp[i][1] dp[i-1][0] nums[i]. 最后返回max(dp[-1][0], dp[-1][1].初始化dp[0][0] 0, dp[0][0][1]nums[0]
python:
二维dp
class Solution:def rob(self, nums: List[int]) - int:dp [[0,0] for _ in range(len(nums))]dp[0][0] 0dp[0][1] nums[0]for i in range(1, len(dp)):dp[i][0] max(dp[i-1][1], dp[i-1][0])dp[i][1] dp[i-1][0] nums[i]return max(dp[-1][0], dp[-1][1])
一维dp
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0: return 0if len(nums) 1: return nums[0]dp [0] * len(nums)dp[0] nums[0] # 将dp的第一个元素设置为第一个房屋的金额dp[1] max(nums[0], nums[1]) # 将dp的第二个元素设置为第一二个房屋中的金额较大者# 遍历剩余的房屋for i in range(2, len(nums)):# 对于每个房屋选择抢劫当前房屋和抢劫前一个房屋的最大金额dp[i] max(dp[i - 2] nums[i], dp[i - 1])return dp[-1] # 返回最后一个房屋中可抢劫的最大金额 213. 打家劫舍 II
思路与打家劫舍Ⅰ的区别在于这个成了一个环状可以想办法把题目转换成打家劫舍Ⅰ。一个思路是分情况考虑一个是考虑第一个房子一个是考虑最后一个房子。然后从两种情况的最大值中选择最大的那个。 python二维dp
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 3:return max(nums)# 不抢劫第一个房屋result1 self.robRange(nums[:-1])# 不抢劫最后一个房屋result2 self.robRange(nums[1:])return max(result1, result2)# 打家劫舍Ⅰdef robRange(self, nums):dp [[0, 0] for _ in range(len(nums))]dp[0][1] nums[0]for i in range(1, len(nums)):dp[i][0] max(dp[i - 1])dp[i][1] dp[i - 1][0] nums[i]return max(dp[-1])
python双指针一维dp
class Solution:def rob(self, nums: List[int]) - int:if not nums: # 如果没有房屋返回0return 0if len(nums) 1: # 如果只有一个房屋返回该房屋的金额return nums[0]# 情况二不抢劫第一个房屋prev_max 0 # 上一个房屋的最大金额curr_max 0 # 当前房屋的最大金额for num in nums[1:]:temp curr_max # 临时变量保存当前房屋的最大金额curr_max max(prev_max num, curr_max) # 更新当前房屋的最大金额prev_max temp # 更新上一个房屋的最大金额result1 curr_max# 情况三不抢劫最后一个房屋prev_max 0 # 上一个房屋的最大金额curr_max 0 # 当前房屋的最大金额for num in nums[:-1]:temp curr_max # 临时变量保存当前房屋的最大金额curr_max max(prev_max num, curr_max) # 更新当前房屋的最大金额prev_max temp # 更新上一个房屋的最大金额result2 curr_maxreturn max(result1, result2)
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。
思路递归加dp
因为是树所以需要遍历。父亲结点是否可以考虑偷考不考虑时的价值如何需要根据左右孩子的状况而定因此需要后序遍历利用左右孩子的状态来决定父亲节点的状态最后根据根节点的状态来得到最高金额。因为偷或不偷那么设置每一个节点的dp数组为dp[0]dp[1], 转移方程为dp[0] 的数值为左右孩子各自max(dp[0], dp[1])的最大值的和dp[1]为左右孩子dp[0]的和加上节点的金额。
python:
class Solution:def rob(self, root: Optional[TreeNode]) - int:final_dp self.backtrack(root)return max(final_dp[0], final_dp[1])def backtrack(self, node):# stop conditionif not node:return [0,0]dp [0,0]left_dp self.backtrack(node.left)right_dp self.backtrack(node.right)dp[0] max(left_dp[0], left_dp[1]) max(right_dp[0], right_dp[1])dp[1] left_dp[0] right_dp[0] node.valreturn dp
