题目
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 1:
1
2
3
4 输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2:
1
2
3
4 输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
动态规划
不能偷窃两间相邻的房屋,也就是说对于一间房屋,选择了偷窃之后,下一间房屋只能选择不偷;而对于一间房屋,如果选择不偷,那么下一间房屋可以选择偷或者不偷。
那么对第一间房屋来说,我该怎么决定偷还是不偷?这样好像不太好决定,因为第二间有可能更多。那么转换思路,假如我偷了第一间,那么只剩下后$N-2$间可以选;而假如我不偷,剩下的$N-1$间我都可以选,问题转化为了:假设我这间房存了$x$元,而后$n$间房可累计偷得的最高金额为$maxf(n)$,那么我可以根据最终偷得金额进行选择,即:$maxf(n)=max(x+maxf(n+2),~f(n+1))$,这样一来我们写出了动态规划的状态转移方程。
顺着以上思路,我们需要从只有最后一间房的情况开始考虑,那么此时必定是偷了总金额最大,只有最后两间房的时候必定偷钱多的那家。基于此初始化动态规划表格。
重新强调一下$maxf(n)$的含义为,序号为$n$及其之后的房屋所能偷得的最大数目,代码如下:
1 | class Solution { |
- 时间复杂度:$O(N)$,因为很明显遍历了
nums
; - 空间复杂度:$O(N)$,使用了长度正比于$N$的数组。
动态规划的空间优化
与斐波那契数列、小青蛙跳台阶问题一样,我们观察到计算窗口的大小仍然为3,因此可以将空间复杂度优化为$O(1)$。
1 | class Solution { |