题解 | #打家劫舍(二)#

环形的家不能同时偷第一个和最后一个。这里家的编号是从1到n。

1 不偷第一个家：

遍历到第i个家时，有两种情况，偷或者不偷，取二者的最大值。i的遍历范围：[3,n]，给定初值: dp1[1]=0, dp[2] = a[2]

dp1[i] = max(dp[i-2]+a[i], dp[i-1])

2 偷第一个家：

遍历到第i个家时，有两种情况，偷或者不偷，取二者的最大值。i的遍历范围：[2,n-1]，给定初值: dp1[0]=0, dp[1] = a[1]

dp1[i] = max(dp[i-2]+a[i], dp[i-1])

这样可以用同一个转移方程

#include <iostream>
using namespace std;
const int N = 2e5+10;
int a[N];
int dp1[N];  //第一家不偷
int dp2[N];  //最后一家不偷
int main() {
    
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    dp1[1] = 0;
    dp1[2] = a[2];
    for(int i = 3;i<=n;i++){
        dp1[i] = max(dp1[i-2]+a[i], dp1[i-1]);                     
    }
    dp2[0] = 0;
    dp2[1] = a[1];
    for(int i=2;i<n;i++){
        dp2[i] = max(dp2[i-2]+a[i], dp2[i-1]);  
    }
    int ans = 0;
    for(int i =1;i<=n;i++){
        if(max(dp1[i],dp2[i])>ans)
            ans = max(dp1[i],dp2[i]);
    }
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")