题解 | #跳台阶#

#先列出规则
#台阶数     跳跃顺序
#1        1
#2        11 2
#3        111 21 12  第三个台阶可以有2种跳法，1、可以看做是以第二个台阶跳一步可以到达第三个台阶，那么跳跃顺序为111 21（跟到达第二台阶方法数一样）。   2、看做从第一个台阶跳两步达到第三个台阶，也就是12。所以第三个台阶总的跳跃方法就是2者相加
#4        1111 211 121 112 22    #第四个台阶也可以如此来看，1、第3个台阶跳一步到达4个台阶，那么跳跃顺序为1111 211 121。  2、第2个台阶跳两步达到第4个台阶，跳跃顺序为112 22。
#规律已经出来了。dp公式：dp[n] = dp[n-1]+dp[n-2]
n = int(input())
if n < 3:
    dp = [1,2]
else:
    dp = [1 for i in range(n)]
    dp[1] = 2
    for i in range(2,n):
        dp[i] = dp[i-1]+dp[i-2]
print(dp[n-1])