【Brush the title】Family robbery

一、题目

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

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额.

示例：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2）,然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的.

二、题解

2.1动态规划

Essentially, what is sought is the maximum cumulative sum of subsequences in the case that adjacent numbers cannot be taken

But this question has a special limitation：

That is, the first number and the last number in the array are considered adjacent,That is, we cannot choose the first number and the last number at the same time,那么我们可以这样做,分两种情况
1）从0~n-2上做选择
2）从1~n-1上做选择
返回两种情况的较大值

源码：
️

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

        dp2[1]=nums[1];
        dp2[2]=nums[2];
        for (int i = 3; i <N ; i++) {
    
            int p1=dp2[i-1];
            int p2=dp2[i-2]+nums[i];
            dp2[i]=Math.max(p1,p2);
        }
        return Math.max(dp1[N-2],dp2[N-1]);
    }

This code can still be optimized,因为dp[i]只依赖dp[i-1]和dp[i-2],So we can use several variable scrolling insteaddp数组

优化后：
️

public int rob(int[] nums) {
    
        if (nums.length == 1) {
    
            return nums[0];
        }
        if (nums.length == 2) {
    
            return Math.max(nums[0], nums[1]);
        }
        int N= nums.length;
        int pre1=nums[0];
        int pre2=Math.max(nums[0],nums[1]);
        for (int i = 2; i < N-1; i++) {
    
            int tmp=Math.max(pre1+nums[i],pre2);
            pre1=pre2;
            pre2=tmp;
        }
        int ans1=pre2;
        pre1=nums[1];
        pre2=Math.max(nums[1],nums[2]);
        for (int i = 3; i < N; i++) {
    
            int tmp=Math.max(pre1+nums[i],pre2);
            pre1=pre2;
            pre2=tmp;
        }
        int ans2=pre2;
        return Math.max(ans1,ans2);
    }