3.13 LeetCode House Robber
题目
给定一个数组nums,代表每家可以打劫到的钱数,连着打劫相邻的两家会自动报警。在保证不报警的前提下,找到可以打劫到的最多钱数。
思路
一开始想,分别奇偶索引求和,最后输出大的,不对,例如[2,1,1,2],取首尾最大。
使用动态规划的思想,到达第i家能获得的最大收益(不一定能打劫)是,max( gain[i-1], gain[i-2] + nums[i] ),不一定要维护整个数组,只需保留最后两个值。
代码
# 思路错,[2,1,1,2],不一定奇偶间隔取最大。
odd = 0
even = 0
for i in range(len(nums)):
if i & 0x001 == 1:
odd += nums[i]
else:
even += nums[i]
return max(odd,even)
# 正确的解法,不维护整个数组,只需保留最后两个值
last = 0
now = 0
for i in nums:
temp = now
now = max(now, last+i)
last = temp
return now
# 另一种直观的写法
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [[0] for _ in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
# rob this house or the previous one
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
进阶1
该题在House Robber的基础上让首位链接形成环,那么即表示第一个和最后一个不能同时被抢,则问题分解为House Robber(nums[0:len(nums)-1])和House Robber(nums[1:len(nums)]),两者中比较大的那个即为结果
代码
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
return max(self.dfs(nums[:-1]), self.dfs(nums[1:]))
def dfs(self, nums):
if len(nums) == 2:
return max(nums[0], nums[1])
gain = [0 for _ in nums]
gain[0] = nums[0]
gain[1] = max(nums[0], nums[1])
for i in range(2,len(nums)):
gain[i] = max(gain[i-1], gain[i-2]+nums[i])
return gain[-1]
进阶2
小偷又发现一个新的可行窃的地点。 这个地区只有一个入口,称为“根”。 除了根部之外,每栋房子有且只有一个父房子。 一番侦察之后,聪明的小偷意识到“这个地方的所有房屋形成了一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
在不触动警报的情况下,计算小偷一晚能盗取的最高金额。
思路
遍历二叉树用递归,
递归关系:如何从rob(root.left),rob(root.right)等等获取rob(root)。
从树根的角度来看,最后只有两个场景:根被抢劫或没有被抢劫。
如果root被抢劫,此时的收获为root的值,加上左右节点不被抢的值
如果root不被抢劫,此时的收获为左右节点能收获的最大值之和(注意此时不一定要抢左右节点,因为没有限制,哪个大就选哪个)。
我们只需要选择产生更多金钱的场景。
递归终止条件:根节点为空,注意因为要传递两个参数,因此返回[0, 0]
代码
def rob(self, root: TreeNode) -> int:
return max(self.treerob(root))
def treerob(self, root):
if root == None:
return [0]*2
gain = [0]*2
left = self.treerob(root.left)
right = self.treerob(root.right)
gain[0] = max(left) + max(right) # 不偷root
gain[1] = root.val + left[0] + right[0]
return gain
上一篇: 46、47-Permutations
下一篇: Token