大盗阿福c++求思路

Question

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有N家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在
不惊动警察的情况下，他今晚最多可以得到多少现金？

Answer 1

-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 ; 
}