记忆化搜索WA了几个点，请大佬帮忙看看，代码简洁

ljx_gkx @ 2023-04-02 13:00:08

#include<iostream>
#include<cstring>

using namespace std;
const int N = 5e3 + 10;
long long f[N];   //记忆化数组！
int n;

int dfs (int u)
{   
    if (u>n) return 0;    
    if (f[u]!=-1) return f[u];
    if (u==n) return f[u]=1;

    f[u] = dfs(u+1) + dfs(u+2);
    return f[u];
}   

int main()
{
    cin >> n;
    memset (f, -1, sizeof(f));

    cout << dfs (0);

    return 0;
}

by lraM416 @ 2023-04-02 13:01:40

要高精度吧

by LEZ2012 @ 2023-04-03 19:06:47

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数 
void hp(int k)//高精度加法，k来存阶数 
{    
    int i;
    for(i=1;i<=len;i++)
     f[k][i]=f[k-1][i]+f[k-2][i];//套用公式 
    for(i=1;i<=len;i++)             //进位 
     if(f[k][i]>=10)
     {
         f[k][i+1]+=f[k][i]/10;
         f[k][i]=f[k][i]%10;
         if(f[k][len+1])len++;
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    f[1][1]=1; f[2][1]=2;         //初始化 
    for(i=3;i<=n;i++)              //从3开始避免越界 
     hp(i);                         
    for(i=len;i>=1;i--)             //逆序输出 
     printf("%d",f[n][i]);
    return 0;
}
求关注（我好像来晚了）