这一题被放在了递归与递推的标签下，但是通过n<=1000的数据量不难推算出如果使用递归，时间复杂度会呈指数级增长。
故个人拙见：使用记忆化搜索是此题的最优解。
先看一组代码。
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int n, s[1005];
5 int main(){
6 cin>>n;
7 for(int q=1; q<=n; q++){
8 s[q]++;
9 for(int z=1; z<=q/2; z++){
10 s[q] += s[z];
11 }
12 }
13 cout<<s[n];
14 return 0;
15 }
在读完题后可先进行手动模拟。以6为例，存在
① 6
② 16
③ 26 126
④ 36 136
可以看出，当 n 为 6 时，s[6] = s[1]+s[2]+s[3]+1。
故从s[1]开始记忆，到 s[n]停止。
But，用ans来表示具有改性质数的个数，手动模拟时，我们会得到一组简单的数据。
n=0，ans=1； n=1，ans=1；
n=2，ans=2； n=3，ans=2；
n=4，ans=4； n=5，ans=4；
n=6，ans=6； n=7，ans=6；
会发现，① n为奇数时，s[n]=s[n-1]，
② n为偶数时，s[n]=s[n-1]+s[n/2]。
③ s[0]=s[1]=1;
那么便可以使用一层循环来解决问题，代码如下：
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int n,s[1005];
5 int main(){
6 s[1]=1;
7 cin>>n;
8 for(int q=2; q<=n; q++){
9 if(q%2 == 0){
10 s[q] = s[q-1] + s[q/2];
11 }else{
12 s[q] = s[q-1];
13 }
14 }
15 cout<<s[n];
16 return 0;
17 }