题解 | 跳台阶

dp算法跳台阶

第一次跳有两种跳法：

第一次跳了一阶，然后只用求后面 n-1阶的跳法；

第一次跳了两阶，然后只用求后面n-2阶的跳法。

假设：n阶台阶跳法为 f(n),可把问题分解为 f(n)=f(n-1)+f(n-2)。

n = int(input())

a = [[1 for _ in range(n)],[0 for _ in range(n)] ]
tmp = [1,2]
for i in range(2,n):
    a[0][i]=(a[0][i-1]+a[1][i-1])%998244353
    a[1][i]=(a[0][i-2]+a[1][i-2])%998244353
    tmp.append((a[0][i]+a[1][i])%998244353)

print(tmp[n-1])