O(n)做法

#include <bits/stdc++.h>
using namespace std;
long long a[1000006],n;
int main() {
	cin>>n;
	a[1]=1;
	a[0]=1;
/*
要问为什么a[0]也要预处理，因为1/2放在int类型会强制转换成0
*/
	for(int i=2;i<=n;i++){
		a[i]=a[i-2]+a[i/2];//递推
	}
	cout<<a[n];//输出
	return 0;
}
/*
0  1
1  2   a[1-2]+a[1/2]
2  2   a[2-2]+a[2/2]
3  2   a[3-2]+a[3/2]
4  4    ……………… 
5  4
6  6
7  6
*/

这题可以用递推做
#include<bits/stdc++.h>
using namespace std;
long n,i,j,s,f[1005];
int main()
{
	cin>>n;
    for(i=1;i<=n;i++)
    {
        f[i]=1;//本身
        for(j=1;j<=i/2;j++)//到i的一半
            f[i]+=f[j];//每次累加
    }
    cout<<f[n];
	return 0;
}
记忆化版
不加记忆化90！
震惊了我都，数据太水！
#include<bits/stdc++.h>
using namespace std;
long n,i,j,s,f[1005];
long dg(long n)
{
	if(n==1)return 1;
	long s=1,i;
	for(i=1;i<=n/2;i++)//思路很简单
	{
		if(!f[i]){
			s+=dg(i);
			f[i]=dg(i);//记忆化
		}
		else s+=f[i];//出现过直接调用
	}
	return s;
}
int main()
{
	cin>>n;
	cout<<dg(n);
	return 0;
}