题解 | 数楼梯

#include <iostream>
using namespace std;
using ll=long long;

/*
f(3)=f(2)+f(1)=2+1=3
f(4)=f(3)+f(2)=3+2=5
实际上f(n)的取值只能由f(n-1)和f(n-2)来确定,
所有有递推关系式:
f(n)=f(n-1)+f(n-2)
跟斐波那契数列差不多
*/

int main() {
    int n;cin>>n;
    int f[n+1];
    f[1]=1;f[2]=2;
    for(int i=3;i<=n;++i){
        f[i]=f[i-1]+f[i-2];
        f[i]%=998244353;
    }
    cout<<f[n];
}
// 64 位输出请用 printf("%lld")