力扣（LeetCode)每日一题 213. 打家劫舍 II

墨蓝 2024-03-02 08:16 14阅读 0赞

题目链接[https://leetcode.cn/problems/house-robber-ii/?envType=daily-question&envId=2023-09-17][https_leetcode.cn_problems_house-robber-ii_envType_daily-question_envId_2023-09-17]

在打家劫舍I的基础上，房屋变成了环，此时第一个和最后一个不能共存。

比较两种情况，哪种的金额最大.

**备注**：博主思考了半天，才想明白：在房间巨多时，这种方式如果第一个和最后一个都不选，是不是有漏洞啊？ 答案是并没有漏，因为如果第一个和最后一个都不选的时候，第二个和倒数第二个房间一定是选了的，此时结果就是最大，没有漏掉！！

想明白情况之后，代码就非常好写啦！ 来看代码：

class Solution {
        public int rob(int[] nums) {
            if(nums.length==1){
                return nums[0];
            }
            if(nums.length==2){
                return Math.max(nums[0],nums[1]);
            }
            int a = dfs(nums,0,nums.length-2);
            int b = dfs(nums,1,nums.length-1);
            return Math.max(a,b);
        }
    
        public int dfs(int[] nums,int start,int end){
            int[] db = new int[nums.length];
            db[start]=nums[start];
            db[start+1]=Math.max(nums[start],nums[start+1]);
            for(int i=start+2;i<=end;i++){
                db[i]=Math.max(db[i-1],nums[i]+db[i-2]);
            }
            return db[end];
        }
    }

![ee725c9955c84da99b113ee786e72988.png][]

时间效率很高！

[https_leetcode.cn_problems_house-robber-ii_envType_daily-question_envId_2023-09-17]: https://leetcode.cn/problems/house-robber-ii/?envType=daily-question&envId=2023-09-17
[ee725c9955c84da99b113ee786e72988.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/3b9c425962d0453296df796c00a4bbbb.png