Daily practice of dynamic programming (3)

打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋.每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警.
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额.

题解：如果房屋数量大于两间,应该如何计算能够偷窃到的最高总金额呢？对于第 k~(k>2)k (k>2) 间房屋,有两个选项：
（1）偷窃第 kk 间房屋,那么就不能偷窃第 k-1k−1 间房屋,偷窃总金额为前 k-2k−2 间房屋的最高总金额与第 kk 间房屋的金额之和.
（2）不偷窃第 kk 间房屋,偷窃总金额为前 k-1k−1 间房屋的最高总金额.
dp[i]=max(dp[i−2]+nums[i],dp[i−1])

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        int n=nums.size();
        if(n==0)
        {
    
            return 0;
        }
        if(n==1)
        {
    
            return nums[0];
        }
        vector<int>dp(n+1);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;i++)
        {
    
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
};

Add a condition to the above question：The first house is next to the last house,That is, the house forms a circle,how to solve the problem？

解题：It can be understood that the first room and the second room cannot be entered at the same time,This can be divided into two parts,There is first room without last room and there is last room without first room,Then compare the larger value between them

class Solution {
    
public:
    int robfun(vector<int>& nums,int start,int end)
    {
       
        int first=nums[start];
        int second=max(nums[start+1],nums[start]);
        for(int i=start+2;i<=end;i++)
        {
       
            int cur=second;
            second=max(second,first+nums[i]);
            first=cur;
        }
        return second;
    }
    int rob(vector<int>& nums) {
    
        int n=nums.size();
        if(n==0)
        {
    
            return 0;
        }
        if(n==1)
        {
    
            return nums[0];
        }
        if(n==2)
        {
    
            return max(nums[0],nums[1]);
        }
        return max(robfun(nums,0,n-2),robfun(nums,1,n-1));
    }
};