记忆化 dfs题解

#include<iostream>
using namespace std;
int s[1000];
int dfs(int n){
    if(s[n-1])return s[n-1];
    if(n==1)return 1;
    if(n%2)return s[n-1]=dfs(n-1);
    return s[n-1]=dfs(n-1)+dfs(n/2);
}int n;
int main(){
    cin>>n;
    cout<<dfs(n);
    return 0;
}