Java开发之我是一个会动态规划的小偷

今天药忘吃喽~ 2021-07-25 02:29 254阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]

## 一、初始化状态 ##

我是一个专业的小偷，遇到这种问题，先从最简单的开始思考

假设房屋数量n = 1时，那么不用说了，最高金额等于这间房屋的现金

假设房屋数量n = 2时，最高金额等于两间房屋中较大金额的那间的现金

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1][]  
假设房屋数量n = 3时，会有几种情况

因为连续偷两间屋子会报警，所以当前这件屋子，要么偷，要么不偷

1）假设我们偷第三间屋子，那么前面只能偷第一间屋子![在这里插入图片描述][20210507215342347.png]  
2）假设我们不偷第三间屋子，那么就相当于偷前两间屋子即n=2的情况![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 2]  
我们取这两种情况的最高金额，也就是

房屋数量n为3的最高金额 = max(前面两间房屋算出的最高金额,第一间屋子金额+第三间屋子金额)

假设房屋数量n= 4时：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 3]  
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)的空间复杂度 , 二维数组可以变成一维数组

我真是太聪明啦！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 4]  
生命不止坚毅鱼奋斗，有梦想才是有意义的追求  
给大家推荐一个免费的学习交流群：  
最后，祝大家早日学有所成，拿到满意offer，快速升职加薪，走上人生巅峰。  
[Java开发交流君样：756584822][Java_756584822]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]: /images/20210724/7fc64b9071024ffdbc8b3f8cc1192c36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1]: /images/20210724/2cd32298527c4c98a50750ef2c1282ed.png
[20210507215342347.png]: /images/20210724/52a6978434dc46f59c449e9a41ec2d7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 2]: /images/20210724/90a324f307ac4f0b81197d0351b1f8b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 3]: /images/20210724/058ab398ec334c5a9e2703bd7a1b4830.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 4]: /images/20210724/f3ac3ccffdde45109def782e7dc5b3de.png
[Java_756584822]: https://jq.qq.com/?_wv=1027&k=0IsBuUb0