在这里插入图片描述
一、初始化状态
我是一个专业的小偷，遇到这种问题，先从最简单的开始思考
假设房屋数量n = 1时，那么不用说了，最高金额等于这间房屋的现金
假设房屋数量n = 2时，最高金额等于两间房屋中较大金额的那间的现金
image
假设房屋数量n = 3时，会有几种情况
因为连续偷两间屋子会报警，所以当前这件屋子，要么偷，要么不偷
1）假设我们偷第三间屋子，那么前面只能偷第一间屋子
在这里插入图片描述
2）假设我们不偷第三间屋子，那么就相当于偷前两间屋子即n=2的情况
在这里插入图片描述
我们取这两种情况的最高金额，也就是
房屋数量n为3的最高金额 = max(前面两间房屋算出的最高金额,第一间屋子金额+第三间屋子金额)
假设房屋数量n= 4时：
在这里插入图片描述
1）假设我们偷当前这间屋子，那么就相当于偷前两间屋子的情况加上当前这间屋子的金额
2）假设我们不偷当前这间屋子，那么就相当于偷前三间屋子的情况
我们取两种情况的最大值，即
f(4) = max(f(2)+第4间屋子金额，f(3))
二、递推公式
我是一个聪明的小偷，很快我就发现，事情其实并不简单
今晚能抢到的最高金额 等于：
1） 偷第n间的情况即前n-2间屋子能抢到的最大金额加上第n间屋子金额
2）不偷第n间的情况即前n-1间屋子能抢到的最大金额
这两种情况中的较大值
即f(n) = max(f(n-2) + 第n间屋子金额，f(n-1))
我忽然发现，计算每一次的状态,从前面的状态来规划下一步的状态，这不就是我学过的动态规划吗？
三、状态缓存
我是一个爱做笔记的小偷，把每次偷的最高金额记下来，我就不需要重复计算啦
用一个数组dp就可以解决啦，即dp[n] = max(dp[n-2] + 第n间屋子金额，dp[n-1])
这种方法的时间复杂度是O(n)，空间复杂度是是O(n)。
python版本代码如下：
class Solution(object):
def rob(self, nums):
if len(nums) == 0:
return 0
if len(nums) <= 2:
return max(nums)
dp = [nums[0],max(nums[0],nums[1])]
for i in range(2,len(nums)):
dp.append(max((dp[i-2] + nums[i]), dp[i-1]))
return max(dp)
四、空间压缩
我是一个精打细算的小偷，很快我又发现，我也不必把每一次计算的金额都记下来，
每次我只需要保留
前面n-2间房屋的算出来的金额 和 前面n-1 间房屋算出来的金额
这两个金额就可以了
这样这种方法的时间复杂度是O(n)，空间复杂度是是O(1)。
python版本代码如下：
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) <= 2:
return max(nums)
m1 = nums[0]
m2 = max(nums[0],nums[1])
for i in range(2,len(nums)):
m1,m2 = m2,max(m1+nums[i],m2)
return m2
我突然发现，这和之前青蛙老弟爬楼梯的题目怎么差不多啊：青蛙爬楼梯
总结
简易动态规划四部曲
1）初始化状态
尝试列出每种状态的情况
2）递推公式
由前面的状态尝试找出规律，推出递推公式
3）状态缓存
将每一次计算出的状态缓存下来,从而为下一步的状态提供记录，通常是一维数组或者二维数组
4）空间压缩
当前状态常常只需要根据前面某些状态进行计算，因此可以不必保留每一次的状态
即一维数组可以变成O(1)的空间复杂度 , 二维数组可以变成一维数组
我真是太聪明啦！
在这里插入图片描述
生命不止坚毅鱼奋斗，有梦想才是有意义的追求
给大家推荐一个免费的学习交流群：
最后，祝大家早日学有所成，拿到满意offer，快速升职加薪，走上人生巅峰。
Java开发交流君样：756584822
网友评论