最开始想到的方法是递归
递归代码在这里！
#include <stdio.h>
int count;
void recur(float n)
{
if(n/2>=1)
{
for(int i=1;i<=n/2;i++)
{
count++;
recur(i);
}
}
}
int main()
{
float n;
scanf("%f",&n);
recur(n);
printf("%d",count+1);
return 0;
}
但是测评发现大部分会TLE，看了很多大佬的解答，得到了以下两种解决方案：
首先是递归优化，点这里！
#include <stdio.h>
int a[1001]={0};
int recur(int n)
{
int sum=1;
if(a[n]!=0)
return a[n];
// if(n/2.0>=1)写这个判断发现好像并没有什么用
// {
for(int i=1;i<=n/2;i++)
{
sum+=recur(i);
}
a[n]=sum;
return a[n];
// }
}
int main()
{
int n;
scanf("%d",&n);
a[1]=1;
printf("%d",recur(n));
return 0;
}
递归的本质就是从上往下，触底才反弹，又从下往上，返回答案，这会导致很多的重复计算，和递推的方向是相反的。如果我们加上一个记忆化搜索（即使用一个数组，存放曾经计算过的结果，下次遇到同样的计算，直接获取结果了），就能解决这个问题了！
然后是递推，再点这里！
#include <stdio.h>
int main()
{
int n,i;
int count[1001]={0,1};
scanf("%d",&n);
for(i=2;i<=n;i++)
{
//找到规律就很简单了：
//当i为奇数时f[i]=f[i-1],当i为偶数时f[i]=f[i-1]+f[i/2]
count[i]=count[i-1];
if(i%2==0)
count[i]+=count[i/2];
}
printf("%d",count[n]);
return 0;
}