题目:大盗阿福
题目描述
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金
输入格式
输入的第一行是一个整数T(T≤50) ,表示一共有T组数据。
接下来的每组数据,第一行是一个整数N(1≤N≤100,000) ,表示一共有N家店铺。第二行是N个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
样例输入
2
3
1 8 2
4
10 7 6 14
样例输出
8
24
暴力做法(DFS枚举效率极低)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, T;
int home[N];
//x 表示当前正在考虑哪家店
int dfs(int x)
{
if(x > n) return 0;
// 两条路,不偷当前x家,那就从x+1家开始考虑;头偷当前x家,那就要从x+2家开始考虑了
else return max(dfs(x + 1), dfs(x + 2) + home[x]);
}
int main()
{
scanf("%d", &T);
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &home[i]);
int res = dfs(1);
printf("%d\n", res);
}
return 0;
}
样例模拟过程
记忆化搜索做法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, T;
int home[N];
int mem[N];
//x 表示当前正在考虑哪家店
int dfs(int x)
{
if(mem[x])return mem[x];
int sum = 0;
if(x > n) sum = 0;
// 两条路,不偷当前x家,那就从x+1家开始考虑;头偷当前x家,那就要从x+2家开始考虑了
//一直递归到最后,然后开始返回两个路选择的最大值
else sum = max(dfs(x + 1), dfs(x + 2) + home[x]);
//记忆化
mem[x] = sum;
return sum;
}
int main()
{
scanf("%d", &T);
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &home[i]);
//每次开始初始值为0
memset(mem, 0, sizeof(mem));
int res = dfs(1);
printf("%d\n", res);
}
return 0;
}
DP做法
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N], dp[N];
int main()
{
int m;
cin >> m;
while(m--){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
dp[1] = arr[1];
for(int i = 2; i <= n; i++){
//dp[i]是两条路洗劫钱数的最优解
//当前位置是洗劫前一个店铺还是前前家店铺加当前店铺 取最大值
dp[i] = max(dp[i-1],dp[i-2] + arr[i]);
}
cout << dp[n] << endl;
}
return 0;
}