python/TangDou/AcWing/Statemachine/1049_0.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int a[N]; //原始数组
int f[N]; //递推结果数组
/*
记忆化搜索
状态转移方程是 前i个数 = max(前i-1个数，前i-2个数 +第i个数)
平时写一下搜索还是挺好的。 (比Dp还快 2ms)
O(n)
*/
int dfs(int u) {
    if (u <= 0) return 0;//注意一下这个边界
    if (f[u]) return f[u];//记忆化搜索的灵魂
    return f[u] = max(dfs(u - 1), dfs(u - 2) + a[u]);
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        //每次重置一下结果数组
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        printf("%d\n", dfs(n));
    }
    return 0;
}