大盗阿福c++求思路
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有N家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在
不惊动警察的情况下，他今晚最多可以得到多少现金？
-DP-
【思路】：DP求出每一个状态的最优值，f[i]为盗窃前i家店铺的最优值，那么f[n]就是盗窃前n家店铺的最优值；
面临的每个抉择就是这个店铺盗还是不盗？那就从盗和不盗中选择一个最优值。
盗：f[i-2]+a[i];为前i-2家店铺的最优值+现在盗的店铺；
不盗：f[i-1]；就是前f[i-1]家店铺的最优值；
最后输出f[n]；
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int f[100009],a[100001];
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=a[i];
}
for(int i=2;i<=n;i++)
{
f[i]=max(f[i-2]+a[i],f[i-1]);
}
printf("%d\n",f[n]);
}
return 0;
}
-递归-
思路:result[i] 表示 有 i 家店铺时能借到的（搞事情） 最大现金数目 ，
num[i]表示在第 i 家店铺能借到的现金数目
对于每家店铺特定都有两状态（偷或者不偷），则result[i] = max(result[i-2]+num[i] , result[i-1]) ;
从前向后递推 每个子问题求出最优解 最后得到最优解result[n]
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;
#define maxn 100000+ 10
int t ;
int n ;
int num[maxn] ;
int result[maxn] ;
int main(){
scanf("%d" , &t) ;
while(t--){
scanf("%d" , &n) ;
for(int i = 1 ; i <= n ; i++ ){
scanf("%d" , &num[i]) ;
}
result[1] = num[1] ; // 如果只有一家店 肯定就偷了
result[0] = num[0] = 0 ; // 有 0 家店 偷出的价值为 0
for(int i = 2 ; i<=n ; i++){
// 对于每一家店铺 都有 偷或者不偷 两种状态 （0 - 1)
result[i] = max(result[i-2] + num[i] , result[i-1]) ;
}
printf("%d\n" , result[n]) ;
}
return 0 ;
}
思路：
#include<bits/stdc++.h>
using namespace std;
int t,n;
int sh[100010],f[100010];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>sh[i];
}
f[1]=sh[1];
f[2]=max(sh[1],sh[2]);
for(int i=3;i<=n;i++)
{
f[i]=max(f[i-1],f[i-2]+sh[i]);
}
cout<<f[n]<<endl;
}
return 0;
}