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

墨蓝 2024-03-02 08:16 41阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关 213. 打家劫舍 II

213. 打家劫舍 II 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。

青旅半醒/ 2024年03月30日 15:48/ 0 赞/ 69 阅读

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

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

墨蓝/ 2024年03月02日 08:16/ 0 赞/ 42 阅读

相关 leetcode: 213. 打家劫舍 II

链接：https://leetcode-cn.com/problems/house-robber-ii/ > 题目你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一

朱雀/ 2023年01月18日 14:25/ 0 赞/ 132 阅读

相关 LeetCode 213. 打家劫舍 II

[213. 打家劫舍 II][213. _ II] Ideas 一开始想到了用DFS，结果只能过52个测试用例，超时就改DP呗。假设偷窃房屋的下标范围是 \[sta

朴灿烈づ我的快乐病毒、/ 2023年01月12日 15:59/ 0 赞/ 198 阅读

相关 213. 打家劫舍 II

题目： [213. 打家劫舍 II][213. _ II] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

浅浅的花香味﹌/ 2022年11月26日 07:39/ 0 赞/ 171 阅读

相关 213. 打家劫舍 II

> 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通

谁借莪１个温暖的怀抱￠/ 2022年10月09日 00:37/ 0 赞/ 152 阅读

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

题目 [https://leetcode.com/problems/house-robber-ii/][https_leetcode.com_problems_house

待我称王封你为后i/ 2022年10月06日 13:58/ 0 赞/ 150 阅读

相关 213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防

桃扇骨/ 2022年08月31日 11:07/ 0 赞/ 168 阅读

相关 leetcode 213 打家劫舍II

题目题目：[213. 打家劫舍 II][213. _ II] 参考题解：[打家劫舍II-代码随想录][II-]、[打家劫舍II-力扣官方题解][II- 1] ---

今天药忘吃喽~/ 2022年08月28日 03:51/ 0 赞/ 156 阅读

相关 leetcode213打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系

缺乏、安全感/ 2021年11月23日 04:54/ 0 赞/ 245 阅读