算法1:(动态规划) $O(n)$
//f[i]表示偷到第i家所能获得的最大价值 f[i] = f[i-1], f[i-2] + a[i]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], f[N], n, T;
int main() {
// cin >> T; scanf读入快了3倍时间
scanf("%d", &T);
while (T--) {
// cin >> n;
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); //cin >> a[i];
f[1] = a[1]; //初始化,一家店肯定是偷走
for (int i = 2; i <= n; ++ i)
f[i] = max(f[i-1], f[i-2] + a[i]);
// cout << f[n] << endl;
printf("%d\n", f[n]);
}
return 0;
}
算法2:() $O(n)$
//f[i]表示偷到第i家所能获得的最大价值,记忆化搜索
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], f[N], n, T;
int dfs(int u) {
if (u <= 0) return 0; //没有第0家商店,返回0
if (f[u]) return f[u];
f[u] = max(dfs(u-1), dfs(u-2) + a[u]);
return f[u];
}
int main() {
scanf("%d", &T);
while (T--) {
memset(f, 0, sizeof f);
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
// f[1] = a[1]; //初始化边界
printf("%d\n", dfs(n)); //搜索一下偷到第n家所能偷到的最大价值
}
return 0;
}