题解 | #斐波那契数列#

import sys

a=int(input())

cache=dict()

def dfs(x):

    if x==1 or x==2:

        return 1

#如果结果已经在cache中了，就直接从之前的取出来

    if x in cache:

        return cache[x]

#如果结果不在cache中，就计算好，然后再提取

    else:

        cache[x]=dfs(x-1)+dfs(x-2)

        return cache[x]

print(dfs(a))