递推

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long f[N], n;
int main() {
	cin >> n, f[0] = f[1] = 1;
	for (int i = 2; i <= n; i ++)
		f[i] = f[i - 2] + f[i / 2];
	cout << f[n] << '\n';
	return 0;
}

#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;
}
/*
6
16 26 36
126 136*/