dp

题目

• 题目给出n个，我们从1个开始分析
  1个房子 dp[1]=nums[1];
  2—- dp[2]=max(nums[1],nums[2]); 不能偷相邻的，所以2选1
  3—- dp[3]=max(dp[3-2]+nums[3],dp[2]); 偷1,3号房子，否则偷2号房子
  即使d[2]=nums[1],也没关系，dp[3]取max后代表的还是偷1,3的值
  得到dp方程 $dp[i]=max(dp[i-1],dp[i-2]+nums[i])$

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

  变形：
• *房屋从一排变成围城一圈**
• *意思是第一个和最后一个房子不能同时偷**
• 思路
• 分两次偷，一次偷[0,n-1],另一次偷[1,n]，然后取最大值，无论这2次偷了首尾没有，都不可能同时偷到第一个和最后一个.

class Solution {
public:
    int rob(vector<int>& nums) {
        int len=nums.size();
        if( len == 0 ) return 0;
        if( len == 1 ) return nums[0];
        if( len == 2 ) return max(nums[0],nums[1]);
        vector<int> dp(len);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<len-1;i++)//一直到倒数第2个
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        int ans=dp[len-2];
        
        dp[1]=nums[1];
        dp[2]=max(nums[1],nums[2]);
        for(int i=3;i<len;i++)
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        ans=max(ans,dp[len-1]);
        return ans;
    }
};