405J1R训练(T636400 数的计算)

pico_fence · 2025-07-21 15:03:27 · 个人记录

正确思路

先来个const int N=1e3+5;再来两个整数变量：a[N],n;再来一个记忆递归：

int f(int n){
    if(n==1){
        return 1;
    }
    if(a[n]!=0){
        return a[n];
    }
    if(n%2==1){
        return f(n-1);
    }
    return a[n]=f(n-1)+f(n/2);
} 

在输入n,最后输出f(n)。

正确代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int a[N];
int f(int n){
    if(n==1){
        return 1;
    }
    if(a[n]!=0){
        return a[n];
    }
    if(n%2==1){
        return f(n-1);
    }
    return a[n]=f(n-1)+f(n/2);
} 
int n;
int main(){
    cin>>n;
    cout<<f(n);
    return 0;
}