题解 | 打家劫舍(二)

/*与一般打家劫舍不同，此题房屋首尾成环，所以1和n不能同时被劫。
分两种情况：int case1=rob(dp,nums,2,n);
           int case2=rob(dp,nums,1,n-1);
比较两种情况，输出较大的情况结果
注意：房屋数量为1时，只能被盗了，需要单列。*/


#include <iostream>
#include <vector>
using namespace std;
int rob(vector<int> dp,vector<int>& nums,int s,int e)
{
    for(int i=s;i<=e;i++)
    {
        if(i==1) dp[i]=nums[i];
        else dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[e];
}
int main() {
   int n;
   cin>>n;

   vector<int> nums(n+1);

   for(int i=1;i<=n;i++)
   {
    cin>>nums[i];
   }
    vector<int> dp(n+1,0);
    if(n==1) {cout<<nums[1]<<endl; return 0;}
    int case1=rob(dp,nums,2,n);
    int case2=rob(dp,nums,1,n-1);

   cout<<max(case1,case2)<<endl;
   return 0;
}
// 64 位输出请用 printf("%lld")