解题思路:
注意事项:运用递归时注意运行时间,采用记忆化搜索可有效避免运行时间超限(即用一串数组来记录递归出来的数据)
参考代码:
#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; //将记忆数组数据归零
}
}
}
0.0分
1 人评分