题解 | 不相邻取数

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
#include <iostream>
#include <vector>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
  int n;
  cin >> n;
  vector<vector<int>> dp(n, vector<int>(2, 0));//---------dp[i][0]表示不加上第i个节点的从后往前到第i个节点的最大值,dp[i][1]表示加上第i个节点的...(其实从前往后也是可以的)
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  dp[n - 1][1] = a[n - 1];//---------初始化最后一位
  for (int i = n - 2; i >= 0; i--){
    dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]);//----------------------状态转移方程,如果这次不选那么下个数选不选都可以
    dp[i][1] = dp[i + 1][0] + a[i];//----------如果这次选下次就一定不能选
  }
  cout << max(dp[0][0], dp[0][1]);
  return 0;
}