LeetCode 198. 打家劫舍
一、题目详情
题目难度:中等
题目描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。
二、示例演示
示例 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 。
三、限制条件
1 <= nums.length <= 100
0 <= nums[i] <= 400
从记忆化搜索到递推
启发思路:
- 选
- 不选
DP新手三部曲:
- 思考回溯怎么写:
- 入参和返回值
- 递归到哪里
- 递归边界和入口
- 改成记忆化搜索
- 1:1翻译成递推
打家劫舍,不能选相邻数字,使得数字加和最大
- 从第一个房子或者最后一个房子开始思考最容易,因为受到制约最小
- 比如,考虑最后一个房子选或者不选:
- 如果不选,问题就变成了n-1 个房子
- 如果选,问题就变成了n-2个房子的问题
- 不断递归思考下去,得到一颗搜索树,每个分叉都是选不选
把刚才的思考过程抽象化:
回溯三问:
- 当前操作:枚举第
i
个房子选不选 - 子问题:从前
i
个房子中得到的最大金额和 - 下一个子问题:
- 不选:从前
i-1
个房子中得到的最大金额和 - 选:从前
i-2
个房子中得到的最大金额和
- 不选:从前
- d f s ( i ) dfs(i) dfs(i)就表示从前
i
个房子得到的最大金额和 - 第和前: d f s ( i ) dfs(i) dfs(i),定义DFS或者DP数组时,只能表示从一些元素算出的结果,而不是一个元素算出来的!
- 得到的金额没有当作入参,而是当成了返回值
回溯写法
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)def dfs(i): # i是房子编号if i < 0: # 没有房子可以偷了return 0 # dfs(i)表示前i个房子能取得的最大金额# dfs(i-1)表示,不选当前i# dfs(i-2) + nums[i]表示,选当前ires = max(dfs(i-1), dfs(i-2) + nums[i])return resreturn dfs(n-1) #从最后一个开始!
__________
超时
由于回溯的时间复杂度是指数级别的
优化思路:
- 剪枝
- res = max(dfs(i-1), dfs(i-2) + nums[i])里面递归调用dfs(i-1)和dfs(i-2)
- 其实dfs(i-1)里面算过一次dfs(i-2)
- 在第一次算时把结果保存下来,要用的时候直接调用
- 把递归计算结果保存:下次递归到同样的入参时,就直接返回先前保存的结果
- 时间复杂度优化到了 O ( n ) O(n) O(n)
递归搜索+保存计算结果=记忆化搜索
- 对于python,要用到@cache ,原理是用一个hashmap记录下入参和对应的返回值
- 对于这份代码可以用数组实现
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)cache = [-1] * ndef dfs(i): # i是房子编号if i < 0: # 没有房子可以偷了return 0 if cache[i] != -1:return cache[i]# dfs(i)表示前i个房子能取得的最大金额# dfs(i-1)表示,不选当前i# dfs(i-2) + nums[i]表示,选当前ires = max(dfs(i-1), dfs(i-2) + nums[i])cache[i] = resreturn resreturn dfs(n-1) #从最后一个开始!
-
复杂度 = 状态个数 O ( n ) O(n) O(n) * 单个状态所需要计算时间 O ( 1 ) O(1) O(1)
-
空间复杂度也是 O ( n ) O(n) O(n)
-
继续优化空间复杂度
-
计算max发生在dfs调用结束后,也就是递归的归过程中。发生了实际计算
-
干脆去掉递归中的递,只计算归的过程
-
也就是自底向上算——递推(自顶向下——记忆化搜搜)
-
1:1翻译成递推:(自下而上)
- dfs ——> f 数组
- dfs(i)=max(dfs(i-1), dfs(i-2)+nums[i])
- ——>
- f[i]=max(f[i-1], f[i-2]+nums[i])
- 需要对i=0、1的情况特殊处理,因为会有特殊下标
- 可以从i=2开始递推,避免出现负数下标
- 也可以对每个下标+2
- f[i+2]=max(f[i+1], f[i]+x)
- 递归 ——> 循环
- 递归边界 ——> 数组初始值
- dfs ——> f 数组
-
但是这样写,会对i=0
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)f = [0] * (n+2) # 前两个位置空着,从i=2开始递推# 1:1翻译记忆化搜索res = max(dfs(i-1), dfs(i-2)+nums[i])for i, x in enumerate(nums):f[i+2] = max(f[i+1], f[i] + x)# 返回值应该是f的最后一个值!下标是n+1或者-1return f[-1]
- 这份代码空间复杂度仍然是 O ( n ) O(n) O(n),
- 如何修改,使其优化?
- 关键递推公式:f[i+2] = max(f[i+1], f[i] + x)
- 也可写作:f[i] = max(f[i-1], f[i-2] + nums[i])
- f[i-1]上一个算的,f[i-2]上上个算出来的
- 即要计算当前f[i],只需要直到上一个状态 f 1 f_1 f1和上上个状态的值 f 0 f_0 f0,实际上不需要记录所有状态!
- n e w F = m a x ( f 1 , f 0 + n u m s [ i ] ) newF = max(f_1, f_0 + nums[i]) newF=max(f1,f0+nums[i])
- 然后更新 f 1 f_1 f1= n e w F newF newF, f 0 f_0 f0= f 1 f_1 f1
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)# 初始化f0和f1都等于0f0 = f1 = 0for i, x in enumerate(nums):new_f = max(f1, f0 + x)f0 = f1f1 = new_freturn new_f #出了for循环new_f是局部变量,应该写f1!
740. 删除并获得点数
- 选某个值val,记录,累加
- 然后删掉所有val+1 val-1的值,不记录,这个值没了
- 相当于选了某个值val,就选不了所有val+1-1的值,
- 这是打家劫舍的影子吧
如何转换成打家劫舍?
- 先统计出nums数组中每个数字出现的次数
- 然后将每个数字与其出现次数乘积结果放入新数组对应位置
- 问题就转化成了:新数组中,相邻元素不能同时选取,求出能获得的最大点数。
- 也就是打家劫舍
这样问题就很简单了!一次就写出来了!
转换数组+打家劫舍+从记忆化搜索到递推
class Solution:def deleteAndEarn(self, nums: List[int]) -> int:new_nums = [0] * (max(nums) + 1)for i in range(len(nums)):new_nums[nums[i]] += nums[i]# 接下来就是打家劫舍问题!f0 = f1 = 0 # 初始化状态for i in range(len(new_nums)):new_f = max(f1, f0 + new_nums[i] )f0 = f1f1 = new_freturn f1
- 注意这里new_nums长度应该是max(nums) + 1,一开始没+1是不对的!
2320.统计放置房子的方式数
以下是关于“2320. 统计放置房子的方式数”这道题的完整内容排版,包括代码、测试用例、测试结果示例,适合发布在CSDN等平台:
《LeetCode 2320. 统计放置房子的方式数 题解及示例》
一、题目详情
题目难度:中等
相关标签:[可填写具体相关算法标签,如“动态规划”等]
相关企业:[若知道常被哪些企业考察可填写]
题目描述:一条街道上共有 n ∗ 2 n * 2 n∗2 个地块,街道的两侧各有 n n n 个地块。每一边的地块都按从1到 n n n 编号。每个地块上都可以放置一所房子。现要求街道同一侧不能存在两所房子相邻的情况,请你计算并返回放置房屋的方式数目。由于答案可能很大,需要对 1 0 9 + 7 10^9 + 7 109+7 取余后再返回。注意,如果一所房子放置在这条街某一侧上的第 i i i 个地块,不影响在另一侧的第 i i i 个地块放置房子。
二、示例演示
示例1:
输入: n = 1 n = 1 n=1
输出: 4 4 4
解释:
可能的放置方式:
- 所有地块都不放置房子。
- 一所房子放在街道的某一侧。
- 一所房子放在街道的另一侧。
- 放置两所房子,街道两侧各放置一所。
三、解题思路
关键点分析
- 本题有两个关键要点:一是街道同一侧不能存在两所房子相邻,这与经典的“打家劫舍”问题类似,都是相邻元素存在某种限制条件;
- 二是街道两侧放置相互独立,互不影响,所以我们可以先单独考虑街道一侧的放置情况,然后再根据两侧独立的性质来计算总的放置方式数。
动态规划思路
- 我们将问题转化为动态规划来解决。设 f [ i ] f[i] f[i] 表示在街道一侧前 i i i 个地块放置房子的方式数。
- 递推公式推导:
- 对于第 i i i 个地块,有两种情况:
- 不放置房子在第 i i i 个地块,那么此时前 i i i 个地块放置房子的方式数就等于前 i − 1 i - 1 i−1 个地块放置房子的方式数,即 f [ i ] = f [ i − 1 ] f[i] = f[i - 1] f[i]=f[i−1]。
- 放置房子在第 i i i 个地块,由于不能与第 i − 1 i - 1 i−1 个地块的房子相邻,所以此时前 i i i 个地块放置房子的方式数就等于前 i − 2 i - 2 i−2 个地块放置房子的方式数,即 f [ i ] = f [ i − 2 ] f[i] = f[i - 2] f[i]=f[i−2]。
- 综合这两种情况,前 i i i 个地块放置房子的方式数就是这两种可能情况的和,所以递推公式为: f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i - 1] + f[i - 2] f[i]=f[i−1]+f[i−2]。
- 对于第 i i i 个地块,有两种情况:
初始化分析
- 当 i = 0 i = 0 i=0 时,
第0个地块
也就是还没有地块,此时有一种放置方式,就是什么都不做,所以 f [ 0 ] = 1 f[0] = 1 f[0]=1。 - 当 i = 1 i = 1 i=1 时,
第1个地块
只有一个地块,那么有两种放置方式,要么放房子,要么不放房子,所以 f [ 1 ] = 2 f[1] = 2 f[1]=2。 - 真的要被 **
第
前
**搞晕了!!!记得从i的定义出发,去思考如何初始化状态!
四、代码实现(Python)
递推版
class Solution:def countHousePlacements(self, n):mod = 10**9 + 7f = [1, 2]for i in range(2, n + 1):f.append((f[i - 1] + f[i - 2]) % mod)return (f[n] * f[n]) % mod
优化空间版
class Solution:def countHousePlacements(self, n: int) -> int:mod = 10 ** 9 + 7# fi表示第i个地块的放置方法# f0表示没有地块,什么也不做 也是一种方案f0 = 1# f1表示有一个地块,可以放或不放,结合f0f1 = 2# 单独看一侧,有n个地块,i=0和1的情况已经解决,从2开始递归# 递归到i=n,表示n个地块的方案才对for i in range(2, n+1): # 从0开始遍历?遍历到n-1?# new_f = f0 + f1# 更新f0为上上步f0 = f1# 更新f1为上步f1 = new_freturn f1 ** 2 % mod
在上述代码中:
- 首先定义了一个常量
mod
,用于对结果取余,以满足题目要求。 - 初始化了列表
f
,其中f[0]
设为1
,f[1]
设为2
,这是根据前面分析的初始化条件来设置的。 - 然后通过循环,根据递推公式
f[i] = f[i - 1] + f[i - 2]
计算f
列表中每个位置的值,并对结果取余。 - 最后,由于街道两侧放置相互独立,所以总的放置方式数是街道一侧放置方式数的平方,返回
(f[n] * f[n]) % mod
。
很好,写出来了,继续打家劫舍!
打家劫舍II
- 偷东西偷到土楼了!?
- 偷看了一眼评论区,关键思路是直接分类讨论[0, n-2] 和[1, n-1]两种情况,手动隔离了首尾相连的难题!然后对比两种情况即可?
class Solution:def rob(self, nums: List[int]) -> int:# 打家劫舍递推公式:f[i]=max(f[i-1],f[i-2]+nums[i])n = len(nums) # 特解,n小于4?if n < 4:return max(nums) # 分类讨论[0, n-2] 和[1, n-1]两种情况f0 = nums[0]f1 = nums[1]# f2 = nums[2]# [0, n-2],i从2开始for i in range(2, n-1):new0_f = max(f1, f0 + nums[i])f0 = f1f1 = new0_f# [1, n-1], i从3开始f11 = nums[1]f22 = nums[2]for i in range(3, n):new1_f = max(f22, f11 + nums[i])f11 = f22f22 = new1_freturn max(f1, f22)
——————————————————————————————————————
解答错误
71 / 75 个通过的测试用例官方题解
输入
nums =
[1,3,1,3,100]添加到测试用例
输出
101
预期结果
103
————————————————————————————————————————————
改为: f22 = max(nums[2], nums[1])后
————————————————————————————————————————————
解答错误
73 / 75 个通过的测试用例
- 问题出在哪了?
- 以上代码思路是:通过分类讨论,分别计算不包含最后一个房屋
[0, n - 2]
和不包含第一个房屋[1, n-1]
这两种情况下能够偷窃到的最高金额,然后取两次结果最大值作为最终答案 - 另一种思路是;
- 定义辅助函数rob1:解决普通的打家劫舍问题
- 调用rob1,分别计算
nums[2:-1] + nums[0](即选了第一个房屋nums[0],相当于考虑了第一个房屋,但是不考虑最后一个房屋的中间部分)
,nums[1:](即不包含第一个房屋的情况)
class Solution:# 198. 打家劫舍def rob1(self, nums: List[int]) -> int:f0 = f1 = 0for x in nums:f0, f1 = f1, max(f1, f0 + x)return f1def rob(self, nums: List[int]) -> int:return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))作者:灵茶山艾府
链接:https://leetcode.cn/problems/house-robber-ii/solutions/2445622/jian-ji-xie-fa-zhi-jie-diao-yong-198-ti-qhvri/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。