import sys

#优化空间复杂度为o(1),变量滚动更新
def climb(n)->int:
    if n==0 or n==1:
        return 1
    f0=1
    f1=1
    for i in range(2,n+1):
        new_f=f0+f1
        f0=f1
        f1=new_f
    return f1

#空间复杂度O（n）
def clim1(n)->int:
    if n==0 or n==1:
        return 1
    dp=[0]*(n+1)
    dp[0]=1
    dp[1]=1
    for i in range(2,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

def main():
    try:
        line=sys.stdin.readline().strip()
        if not line:
            return
        nums=list(map(int,line.split()))
        n=nums[0]
        res=climb(n)
        print(res)
        return
    except ValueError:
        return


if __name__=="__main__":
    main()

思路：

        每次只允许爬1步或者2步，请问爬到n阶台阶共有多少种方案？使用dp数组，dp[i]表示，爬到i阶台阶，共有dp[i]种方案。递推式：dp[i]=dp[i-1]+dp[i-2]

        扩展：如果可以爬1步或者2步或者3步，爬到n阶台阶有多少种方案？递推式为：dp[i]=dp[i-1]+dp[i-2]+dp[i-3]