题解 | #打家劫舍(二)#
打家劫舍(二)
https://www.nowcoder.com/practice/6a8b2ceb3f8f4e5891939d7d7cbbd2c4
环形的家不能同时偷第一个和最后一个。这里家的编号是从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")
文远知行公司福利 555人发布