DP1 斐波那契数列

描述
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.fib(x)={ 
1
fib(x−1)+fib(x−2)

  
x=1,2
x>2

  的数列
数据范围：1\leq n\leq 401≤n≤40
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法

输入描述：
仅输入一个正整数 n。
输出描述：
输出斐波那契数列中第 n 个数。
示例1
输入：
4
复制
输出：
3
复制
说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。   
示例2
输入：
1
复制
输出：
1
复制
示例3
输入：
2
复制
输出：
1




def dfs(x):
    temp=[1,1,1]
    if x==1&nbs***bsp;x==2:
        temp.append(1)
        temp.append(1)
    else:        
        for i in range(3,x+1):
            temp.append(temp[i-1]+temp[i-2])
    return temp[-1]   
while True:
    try:
        n=int(input())
        result=dfs(n)
        print(result)
    except:
        break