大盗阿福（记忆化搜索）

解题思路:

注意事项:运用递归时注意运行时间，采用记忆化搜索可有效避免运行时间超限（即用一串数组来记录递归出来的数据）

参考代码:

#include<stdio.h>

#include<stdlib.h>

int sum=0;

int data[100]={0};

int f(int n,int *a)

{

if(data[n]!=0)

    return data[n];

else if(n==0)

    sum = 0;

else if(n==1)

    sum = a[1];

else {

    int one=0;

    int two=0;

    one=a[n]+f(n-2,a);//此题的两种情况 1（该店被偷）即该店的钱财+空一格门店的钱财 

    two=f(n-1,a);        // 2（该店不被偷）紧挨门店的钱财；

    sum=one>two? one:two;

}

    data[n]=sum;

    return sum;

}

int main()

{

int t;

scanf("%d",&t);

while(t>0)

{ 

int n;

scanf("%d",&n);

int a[n+1];

for(int i=1;i<=n;i++)

    scanf("%d",&a[i]);

    printf("%d\n",f(n,a));

    t--;

for(int i=0;i<=100;i++)

{                            

    data[i]=0;                    //将记忆数组数据归零

}

}

}