House Robber系列

House Robber

链接:198. House Robber

题意:

​ 一个专业小偷打算去偷某条街上的房子,每个房子藏有一定量的金钱,不过相邻的房子间装有报警系统,所以如果你偷了两个相邻的房子,报警系统就会被激活,小偷就会被警察带走。现在要求你给小偷安排一个方案,让他能够偷到最多的钱,同时不被警察带走。

​ 其实就是:给定一个非负数整数数组,求一个子序列a,要求序列中的元素在原数组互不相邻,求使得sum(a)最大的子序列a。

分析:

这个问题具有最优子结构性质,所以我们从头到尾遍历一次数组即可,注意:

  • 每个房子有偷和不偷两个方案
  • 如果偷了房子i,则房子i+1和房子i-1都不能偷

所以转移方程为,dp[i] 表示 房子 0~i 所能偷到的最大价值:

dp[i] = max(dp[i - 1] , dp[i - 2] + x[i])

边界是i - 1 < 0i - 2 < 0 ,此时的dp 值为0

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [0] * len(nums)
for (i, v) in enumerate(nums):
dp[i] = max(dp[i - 2] + v if i - 2 >= 0 else 0, dp[i - 1] if i - 1 >= 0 else 0, v)
return max(dp)

House Robber II

链接:213. House Robber II

题意:

​ 在第一题的基础上,第一间房子和最后一件房子也是连着的,也就是说,房子构成了一个环。

分析:

​ 构成环后,第一个房子和最后一个房子同时偷的情况是不被允许的,所以我们只能取其中一个。

​ 假设把第一间房子从环上挖掉,就退化到了问题1,求出此时的价值为$V_1$

​ 假设把最后一间房子从环上挖掉,就也退化到了问题1,求出此时的价值为$V_2$

​ 那么答案就是两者中最大的那个。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
elif n == 1:
return nums[0]
no_0, no_n = self.lineRob(nums, 1, n), self.lineRob(nums, 0, n - 1)
return max(no_0, no_n)


def lineRob(self, nums, left = 0, right = 0):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n== 0:
return 0
elif n == 1:
return nums[0]
dp, left, right = [0] * n, max(left, 0), min(right, n)

for i in range(left, right):
v = nums[i]
dp[i] = max(dp[i - 2] + v if i - 2 >= left else 0, dp[i - 1] if i - 1 >= left else 0, v)
return max(dp)

House Robber III

链接:337. House Robber III

题意:

​ 好了,小偷偷完那条街后,来到了一个新地方,他发现这个地方的房子布局是一个二叉树的结构,此时如果父亲和孩子节点同时被偷,报警系统就会被拉响。

分析:

​ 跟第一题思路类似,每个节点有偷和不偷两种情况,从树底往上计算即可得到根节点的所得的最大值,所以我们需要做后序遍历,先计算两个孩子的 dp

AC代码:

每一个节点有两个状态,偷和不偷,这两个状态都对应有一个最大值,我用left[0] 表示左孩子不偷时,左孩子的最大值,left[1] 表示左孩子被偷时的最大值。那么对于父亲节点来讲:

  • 如果父亲被偷,则孩子就不能被偷了,此时价值为 left[0] + right[0] + node.val
  • 如果父亲没被偷,则孩子偷不偷无所谓,只要价值最大就行,所以价值为max(left) + max(right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = self.tryRob(root)
return max(res)


def tryRob(self, node):
if not isinstance(node, TreeNode):
return [0, 0]
ans = [0, 0] # max value of (0 means not rob this node, 1 means rob this node)
left = self.tryRob(node.left)
right = self.tryRob(node.right)
ans[0] = max(left) + max(right)
ans[1] = left[0] + right[0] + node.val
return ans
坚持原创文章分享,您的支持将鼓励我继续创作!