当前位置：首页 > article >正文

day-81 打家劫舍 II

article 2024/11/7 19:58:19

在这里插入图片描述
思路
与LCR 089. 打家劫舍相比，本题所有房屋围成了一圈，那么第一间房子和最后一间房子不能同时打劫，那么就可以分为两种情况：1.选第一间房打劫；2.选最后一间房打劫

解题过程
然后依次计算出以上两种情况的最大金额（思路LCR 089. 打家劫舍一样），返回较大值即可

Code

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        int dp1[]=new int[n];
        dp1[0]=nums[0];
        dp1[1]=nums[0];
        for(int i=2;i<n-1;i++){
            dp1[i]=Math.max(dp1[i-2]+nums[i],dp1[i-1]);
        }
        int dp2[]=new int[n];
        dp2[0]=0;
        dp2[1]=nums[1];
        for(int i=2;i<n;i++){
            dp2[i]=Math.max(dp2[i-2]+nums[i],dp2[i-1]);
        }
        return Math.max(dp1[n-2],dp2[n-1]);
    }
}

作者：菜卷
链接：https://leetcode.cn/problems/house-robber-ii/solutions/2980878/da-jia-jie-she-iichao-yue-100-by-ashi-ji-mmb9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。