#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        f=[1 for _ in range(n+1)]
        for i in range(1,n+1,1):
            if(i==1&nbs***bsp;i==2):
                f[i]=1
            else:
                f[i]=f[i-1]+f[i-2]
        return f[n]

自调用也可实现，且代码更简洁，但更耗时 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<0:
            return -1
        if(n==1&nbs***bsp;n==2):
            return 1
        else:
            return self.Fibonacci(n-1)+self.Fibonacci(n-2)