leetcode 213. House Robber II | 213. 打家劫舍 II（Java）

待我称王封你为后i 2022-10-06 13:58 180阅读 0赞

## 题目 ##

[https://leetcode.com/problems/house-robber-ii/][https_leetcode.com_problems_house-robber-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

这道题是「198. 打家劫舍」的进阶，和第 198 题的不同之处是，这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。

和第 198 题相似，这道题也可以使用动态规划解决。建议读者首先阅读 [leetcode 198. 打家劫舍（最简单的动态规划问题）][leetcode 198.]，了解动态规划的思想。

由于本题 **首尾相连**，所以需要注意的是，**首尾不能同时偷**。

思路是，对 **是否选择首元素** 进行分类讨论，分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。

class Solution { 
        public int rob(int[] nums) { 
            int len = nums.length;
            int[] dp1 = new int[len];
            int[] dp2 = new int[len];
            if (len == 1) return nums[0];
            if (len == 2) return Math.max(nums[0], nums[1]);
    
            // dp1 允许选首元素
            dp1[0] = nums[0];
            dp1[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < len; i++) { 
                dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
            }
            // 如果同时选了首尾元素 此时dp1的最大值要删掉尾元素（删掉首元素的情况被包含在dp2中来讨论）
            // else 说明没有同时选首尾元素 此时dp1最大值不变
            if (dp1[len - 1] > dp2[len - 1] && dp1[len - 1] == dp1[len - 3] + nums[len - 1])  
                dp1[len - 1] = dp1[len - 2];
    
            // dp2 强制不选首元素
            dp2[0] = 0;
            dp2[1] = nums[1];
            for (int i = 2; i < len; i++) { 
                dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
            }
    
            return Math.max(dp1[len - 1], dp2[len - 1]);
        }
    }

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

[https_leetcode.com_problems_house-robber-ii]: https://leetcode.com/problems/house-robber-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/c5994e0f64ec467fb916ab175e08a6b1.png
[leetcode 198.]: https://blog.csdn.net/sinat_42483341/article/details/107534093
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/22a81894a5274cd5b62bb8e41b992c11.png