题解 | 不相邻取数
不相邻取数
https://www.nowcoder.com/practice/a2be806a0e5747a088670f5dc62cfa1e
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;
//const int N=;
int main()
{
IOS
int n;
cin>>n;
vector<int> a(n), f(n);
LL s1=0, s2=0, x;
cin>>x; f[0]=x;
cin>>x; f[1]=x;
cin>>x; f[2]=f[0]+x;
for(int i=3; i<n; i++){
cin>>x;
f[i]=max(f[i-2], f[i-3])+x;
}
cout<<max(f[n-1], f[n-2]);
return 0;
}
动态规划，间隔的话就是间隔一个或间隔两个最优（因为间隔三个就可以多选中间的了）
我代码里单独处理的f[0-3]因为更新时会有i-3防止越界
投递腾讯等公司10个岗位
顺丰集团工作强度 274人发布