面试常遇的打家劫舍问题你学会了吗~
打家劫舍I
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1，2，3，1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
分析问题
首先，我们先将问题简化处理。假设目前只有一间房屋，则偷窃该房屋，此时就是偷窃到的最高总金额。如果只有两间房屋，因为此时两间房屋相邻，只能偷窃其中的一间房屋，可以选择其中金额较高的房屋进行偷窃，就是可以偷窃到的最高总金额。如果房屋的数量大于两间，假设小偷此时处于第k（k>2）间房屋，那么他有两个选择。
- 如果他偷窃第k间房屋，那么他就不能偷窃第k-1间房屋，此时其能偷窃到的总金额为前k-2间房屋的最高总金额和第k间房屋的金额之和。
- 如果他不偷窃第k间房屋，那么此时其能偷窃到的总金额为前k-1间房屋的最高总金额。
在上述两个选项中选择金额较大的即为前k间房屋能偷窃到的最高总金额。
我们用 dp[i] 来表示前 i 间房屋能偷窃到的最高总金额，经过前面的分析，可以知道其状态转移方程为：
下面我们来看一下边界条件。
- 当只有一间房屋时，此时dp[0] = nums[0]，表示偷窃该房屋。
- 当只有两间房屋时，此时 dp[1] = max(nums[0] , nums[1])，即在这两间房屋中选择金额较大的房屋进行偷窃。
下面我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#如果数组为空，则直接返回0
if not nums:
return 0
length = len(nums)
#如果房屋数量等于1
#则直接偷窃第一间房屋，
#所以此时能偷窃到的最大金额是nums[0]
if length == 1:
return nums[0]
dp = [0] * length
#边界条件
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, length):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[length - 1]
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
通过观察，我们发现dp[i] 只和 dp[i-2] 和 dp[i-1]有关，即只和该房屋的前两间房屋的最高总金额相关，所以我们可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额即可，从而降低空间复杂度。我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#如果数组为空，则直接返回0
if not nums:
return 0
length = len(nums)
#如果房屋数量等于1
#则直接偷窃第一间房屋，
#所以此时能偷窃到的最大金额是nums[0]
if length == 1:
return nums[0]
#边界条件
first, second = nums[0], max(nums[0], nums[1])
for i in range(2, length):
first, second = second, max(first + nums[i], second)
return second
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
打家劫舍II
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
分析问题
这道题和上一道的不同之处在于房屋的首尾是相连的，即第一间房屋和最后一间房屋是相邻的，因此它们不能被同时偷窃。
我们也可以和上一道题的思路一样，采用动态规划的方法来求解。首先先将问题简单化，假设此时只有一间房屋，则偷窃该房屋，此时就是偷窃到的最高总金额。如果只有两间房屋，因为此时两间房屋相邻，只能偷窃其中的一间房屋，可以选择其中金额较高的房屋进行偷窃，就是可以偷窃到的最高总金额。
到这里我们可以注意到，当房屋数量不超过两间时，最多只能偷窃一间房屋，因此我们不需要考虑首尾连接的问题。但是，如果房屋数量大于二间时，就必须要考虑该限制条件了，即第一间房屋和最后一间房屋不能同时被偷窃。那么如何才能保证第一间房屋和最后一间房屋不能同时被偷窃呢？这里可以分情况来讨论。
- 如果偷窃了第一间房屋，那么就不能偷窃最后一间房屋，因此可以偷窃的房屋的范围是第一间房屋到倒数第二间房屋。
- 如果偷窃了最后一间房屋，那么就不能偷窃第一间房屋，因此可以偷窃的房屋的范围是第二间房屋到最后一间房屋。
我们假设数组 nums 的长度为n。如果不偷窃最后一间房屋，则可以偷窃的房屋的下标是0n-2；如果不偷窃第一间房屋，则可以偷窃的房屋的下标是1n-1。
接下来我们就可以采用上一题的解法，对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。
下面我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#求nums[start,end]范围内可以偷窃到的最大金额
def help(start, end):
first = nums[start]
second = max(nums[start], nums[start + 1])
for i in range(start + 2, end + 1):
first, second = second, max(first + nums[i], second)
return second
length = len(nums)
#边界条件
if length == 1:
return nums[0]
elif length == 2:
return max(nums[0], nums[1])
else:
return max(help(0, length - 2), help(1, length - 1))
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
打家劫舍III
问题描述
在上次打劫完一条街道和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父”房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
示例：
输入：[3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出：7
解释：小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7。
分析问题
首先我们把该问题转化一下，该问题其实是求：对于一棵二叉树来说，树上的每个点都有对应的权值，并且每个点有两种状态（选中和不选中），在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
首先我们用f(a)来表示选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。g(a)表示在不选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。l 和 r 分别表示a的左右孩子。
小偷对于树中的每个节点都有偷或者不偷两种选择，假设当前的节点是a。
- 当a被选中时，a的左右孩子都不能被选中，所以a被选中的情况下，它的子树上被选择的节点的最大权值和为l 和 r 不被选中的最大权值和相加，即 f(a) = g(l) + g(r)。
- 当a不被选中时，a的左右孩子可以被选中，也可以不被选中。此时 g(a) = max { f(l) , g(l) } + max{ f(r) , g(r) }。
这里我们可以使用深度优先搜索的办法后序遍历这棵二叉树，就可以得到每一个节点的 f 和 g。根节点的 f和 g 的最大值就是我们要找的答案。
下面我们来看一下代码的实现。
class Solution:
def __init__(self):
self.f={}
self.g={}
def dfs(self,node):
if not node:
return
self.dfs(node.left)
self.dfs(node.right)
#表示选中该节点
self.f[node]=node.val + self.g.get(node.left,0) + self.g.get(node.right,0)
#表示没有选择该节点
self.g[node] = max(self.f.get(node.left,0),self.g.get(node.left,0)) \
+ max(self.f.get(node.right,0),self.g.get(node.right,0))
def rob(self, root):
self.dfs(root)
return max(self.f.get(root,0),self.g.get(root,0))
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
这里我们还可以优化一下，因为无论是求 f(a) 还是 g(a)，他们的值只和 f(l) 、g(l)、f(r)和g(r)有关。所以对于每一个节点，我们只关心它的左右孩子的 f 和 g 是多少。在python中，我们可以用元组来表示，每次递归返回的时候，都把这个点对应的 f 和 g 返回给上一级调用。这样我们就可以省去哈希表的空间，下面我们来看一下具体的代码实现。
class Solution:
def dfs(self,node):
if not node:
return (0,0)
left=self.dfs(node.left)
right=self.dfs(node.right)
#表示选中该节点
selected = node.val + left[1] + right[1]
#表示没有选择该节点
noselected = max(left[0],left[1]) \
+ max(right[0],right[1])
return (selected,noselected)
def rob(self, root):
result=self.dfs(root)
return max(result[0],result[1])
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
