题解 | #斐波那契数列#

这里使用递归的话，时间复杂度为$O(2^n)O(2^n)$，超时了，因此我们只能使用for循环，具体如下

def fib(n):
    assert n>0
    a,b = 0, 1
    for i in range(1, n+1):    
    	a,b = b, a+b
    return a
n = int(input())
print(fib(n))