Leetcode-213. house raiding II

Dynamic programming (dp)

---

Topic details

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .
Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm device , The maximum amount you can steal tonight .

---

Example 1：

 Input ：nums = [2,3,2]
 Output ：3
 explain ： You can't steal first  1  House No （ amount of money  = 2）, And then steal  3  House No （ amount of money  = 2）,  Because they are next to each other .

Example 2:

 Input ：nums = [1,2,3,1]
 Output ：4
 explain ： You can steal first  1  House No （ amount of money  = 1）, And then steal  3  House No （ amount of money  = 3）.
      Maximum amount stolen  = 1 + 3 = 4 .

Example 3:

 Input ：nums = [1,2,3]
 Output ：3

Ideas :
and leetcode-198. The only difference between the first and last families is that they are adjacent
At this point, let's discuss which one the first and last stole
Steal the head, not the tail , Steal the tail but not the head
198 See :
leetcode-198. raid homes and plunder houses
Integrated the first 198 How to solve the problem , The code is as follows :

My code ：

class Solution 
{
    
public:
    // I use it directly here 198 The method after optimizing the space of the problem 
    int Rob(vector<int>& nums, int start, int end)
    {
    
        int pre2 = 0, pre1 = 0, cur;
        for (int i = start; i < end; ++i)
        {
    
            cur = max(pre2 + nums[i], pre1);	
            pre2 = pre1;						
            pre1 = cur;							
        }
        return cur;
    }
    int rob(vector<int>& nums) 
    {
    
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int rob1 = Rob(nums, 0, n-1); // Steal the head, not the tail 
        int rob2 = Rob(nums, 1, n);   // Steal the tail but not the head 
        return max(rob1, rob2);       // Returns a larger value 
        
    }
};

Knowledge points involved :

1. Dynamic programming (dp)