213. 打家劫舍 II（动态规划）

爱被打了一巴掌 2023-10-05 18:21 5阅读 0赞

#### 213. 打家劫舍 II ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
提示：

*  1 <= nums.length <= 100
 *  0 <= nums\[i\] <= 1000

## 解题思路 ##

本题和198题没有太大的差距，只不过是个环而已。我们还是老样子，找出有几种状态：  
①偷第一家就不能偷最后一家  
②偷最后一家就不可以偷第一家  
这是两种大状态，上面两种状态保证了我们可以首尾不相连，也就是打断了环。既然环断了，那是不是就是198题一样的了。  
所以我们只需要把两种情况的数组传递给辅助函数，再取两种情况中值大的哪一个。  
辅助函数作用就是198题的解题方法

## 代码 ##

class Solution {
        
         public int rob(int[] nums) {
        
            if (nums.length == 0) {
        
                return 0;
            }
            if (nums.length == 1) {
        
                return nums[0];
            }
    
            int[] case1 = Arrays.copyOfRange(nums, 0, nums.length - 1);//不偷最后一家
            int[] case2 = Arrays.copyOfRange(nums, 1, nums.length);//不偷第一家
    
            return Math.max(help(case1), help(case2));
    
        }
    
        //像小偷第一版【198题】一样，求出可以抢到的最多的财富，注意并不是环，只是普通数组
        public int help(int[] nums) {
        
    
            int N = nums.length;
            int[] dp = new int[N + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for (int i = 2; i <= N; i++) {
        
                //198题的状态转移方程
                dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
            }
    
            return dp[N];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210124164813306.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70