1028记忆化搜索和dp**

/*
记忆化搜索要画树形图更好理解

#include<bits/stdc++.h>
using namespace std;
int f[10000];
int dfs(int x){
    if(f[x]) return f[x] ;//如果已经算过就直接返回
    f[x]=1;
    for(int i=1;i<=x/2;i++){//比如说x=6哪它下面会有三个分支
         f[x]+=dfs(i);
    //这里要把i传进去而不是x
    }
    return f[x];
}
int main(){
    int n;
    cin>>n;
   int t= dfs(n);
    cout<<t;
    return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,f[1005]={0,1,2};
    cin>>n;
    for(int i=3;i<=n;i++){
        if(i%2==1)f[i]=f[i-1];//当i为奇数时能形成的组合数和i-能形成的组合数一样多
        else f[i]=f[i-1]+f[i/2];//这里减二和减一差不多
    }
    cout<<f[n];
    return 0;
}