用递归写的，50分，求教！！！

ZJLmath @ 2022-08-27 13:16:35

#include<iostream>
using namespace std;
int f(int h){
    if(h==0)return 0;
    if(h==2)return 2;
    if(h==1)return 1;
    return f(h-1)+f(h-2);
}
int main(){
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

by LAICZ @ 2022-08-27 13:20:32

递归会爆栈空间/TLE，原因是重复计算。

可以使用kkksc03数组，每次求解时更新数组

如果更新了就直接套用值，不用再计算了

by _Give_up_ @ 2022-08-27 13:21:22

@ZJL1020math 还要高精度

by LAICZ @ 2022-08-27 13:23:34

#include<iostream>
using namespace std;
int kkksc03[114514];
int f(int h){
    if(kkksc03[h]!=-1)return kkksc03[h];
    if(h==0)return 0;
    if(h==2)return 2;
    if(h==1)return 1;

    kkksc03[h] = f(h-1)+f(h-2);
    return kkksc03[h]
}
int main(){
    memset(kkksc03,-1,sizeof(kkksc03);
    kkksc03[0]=0;
    kkksc03[1]=1;
    kkksc03[2]=2;
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

by _Give_up_ @ 2022-08-27 13:24:04

用递推不加高精度是60

#include<bits/stdc++.h>
#define int long long

using namespace std;

int a[100010];

signed main()
{
    int n;
    a[0]=1,a[1]=2;
    for (int i=2;i<100010;i++)
    {
        a[i] = a[i-1]+a[i-2];
    }
    cin >> n;
    cout << a[n-1] << endl;
    return 0;
}

by _Give_up_ @ 2022-08-27 13:24:52

@LAICZ 编译都没过……

by ZJLmath @ 2022-08-27 13:29:23

谢神犇指点

by LAICZ @ 2022-08-27 13:31:58

@Stephen_Curry_II 我在讨论区手写的，所以重点不是程序的思想吗？

by _Give_up_ @ 2022-08-27 13:36:42

@LAICZ 这道题用递推，你这和没改一样