题解 | 跳台阶

//跳台阶
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf=998244353;
int n;
int v[200005];
int f(int x, int v[])
{
    if(x==2) return 1;
    if(x==3) return 2;
    if(v[x]!=-1) return v[x];
    v[x]=(f(x-1,v)+f(x-2,v))%inf;
    return v[x];
}
int main()
{
    cin>>n;
    memset(v,-1,sizeof v);
    v[1]=0;
    v[2]=1;
    v[3]=2;
    cout<<f(n,v)<<'\n';
    return 0;
}