每日一题 | Python3 实战 LeetCode 「198. 打家劫舍 」& 「213. 打家劫舍 II」
每日一题 | Python3 实战 LeetCode 「198. 打家劫舍 」& 「213. 打家劫舍 II」
198. 打家劫舍 & 213. 打家劫舍 II
题目链接
https://leetcode-cn.com/problems/house-robber/
也可以点击「阅读原文」直达题目链接。
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 400
解题思路
这道题是标准的动态规划的题目。但是对于之前没有接触过动态规划或者对动态规划不熟悉的同学来说（比如说我），还是有一定的难度的。因此我刚开始用的是暴力搜索的方法，不出意外的超时了。后面加上剪枝的过程后，勉强通过。
不过呢，动态规划早晚都是要学的，刚好趁这个机会，也记录下自己的学习过程。
其实动态规划的理论，很多人应该都不陌生，首先是状态定义、然后是状态转移方程，还有就是边界情况。理论大家都知道，但是碰到题目的还是一脸懵逼。
我觉得出现这种情况的原因还是自己见的动态规划的题目比较少，一看到是动态规划的题目，就望而却步，放弃了。
不过这次下定决心，掌握基本的算法。所以只能咬着牙坚持下去了。
对于这道题的话，因为不能偷盗相邻的房间，因此，对于当前房间来说，如果偷盗当前房间，那么前一个房间是不能偷盗的。
这是一个很重要的点，如果我们定义一个数组 dp，然后 dp[i] 表示到当前房间所能偷盗的金额的最大值的话，那么
这就是本题的状态转移方程，以及状态定义了。不要问是怎么想到的。。。
代码
暴力搜索代码：超时
class Solution:
def rob(self, nums: List[int]) -> int:
self.ans = 0
if len(nums) > 0:
self.dfs(0, nums, 1, 0)
self.dfs(1, nums, 1, nums[0])
return self.ans
def dfs(self, index, nums, cur, res):
if cur == len(nums):
if res > self.ans:
self.ans = res
return
if index == 0:
self.dfs(1, nums, cur + 1, res + nums[cur])
self.dfs(0, nums, cur + 1, res)
搜索 + 剪枝：通过
class Solution:
def rob(self, nums: List[int]) -> int:
self.ans = 0
self.state = [[0 for _ in range(len(nums))] for _ in range(2)]
print(self.state)
if len(nums) > 0:
self.dfs(0, nums, 1, 0)
self.dfs(1, nums, 1, nums[0])
return self.ans
def dfs(self, index, nums, cur, res):
if cur == len(nums):
if res > self.ans:
self.ans = res
return
if index == 0:
if res + nums[cur] > self.state[1][cur - 1]:
self.state[1][cur - 1] = res + nums[cur]
self.dfs(1, nums, cur + 1, res + nums[cur])
if res > self.state[0][cur - 1]:
self.state[0][cur - 1] = res
self.dfs(0, nums, cur + 1, res)
动态规划：通过
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
dp = [0] * (size + 1)
dp[1] = nums[0]
for i in range(2, size + 1):
dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
return dp[-1]
动态规划 + 空间优化：通过
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
first, second = 0, nums[0]
for i in range(2, size + 1):
first, second = second, max(second, first + nums[i - 1])
return second
复杂度分析
这里只对动态规划解法进行分析。
动态规划：
时间复杂度：
空间复杂度：
动态规划 + 空间优化
时间复杂度：
空间复杂度：
另外，力扣上还有一道题，是这道题的升级版，它就是 「213.打家劫舍II」,题目链接如下：
https://leetcode-cn.com/problems/house-robber-ii/
这道题比上个题目多的要求就是这次的屋子假是首尾相连的，也就是说偷盗第一间房屋的话，就不能偷盗最后一间房屋了（只有一间房屋的时候除外），因此我们可以将这次的偷盗看成两部分来进行看待，第一部分就是只偷盗除了最后一间屋子时的情况，第二种情况就是不考虑偷盗第一间屋子，只考虑偷盗剩下的屋子。然后这两部分的最大值就是结果。
代码
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
return max(self.rob_(nums[:-1]), self.rob_(nums[1:]))
def rob_(self, nums: List[int]) -> int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
first, second = 0, nums[0]
for i in range(2, size + 1):
first, second = second, max(second, first + nums[i - 1])
return second
复杂度分析
时间复杂度：
空间复杂度：
好了，今天的内容就到这里了。我最近在学习数据结构与算法的相关知识，也会在力扣进行每日一题的打卡。如果你最近在求职面试或者也在进行力扣进行每日一题的打卡的话，欢迎加入我们，后台回复「加群」即可。我一直坚信一个人走的更快，一群人走的更远。很多时候，只要坚持下去了，那么你就超越了很多人。
参考资料
- https://leetcode-cn.com/problems/house-robber/solution/yu-ni-yi-qi-xue-suan-fa-python3-shi-xian-knk6/
- https://leetcode-cn.com/problems/house-robber-ii/solution/yu-ni-yi-qi-xue-suan-fa-python3-shi-xian-ifpb/
- https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/