题解 | #斐波那契数列#

from re import S
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    dict={}
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n==1:
            return 1
        elif n==2:
            return 1
        elif n>2:
		#在n>2的情况下主要是将重复计算的值，保存到字典中
		#例如在计算F5的时候，会分别求f(4)和F(3),计算F（4）的时候会去求F（3）和F（2），相当于计算了2次
		#f(3)这时候，需要把F3的值记录入字典中，然后再用字典返回n的值即可
		几乎可以说，俩个F（N)函数都在求，转化为一个FN函数求，求完后保存到字典中另一个fN函数直接可可用
            if n not in self.dict.keys():
                self.dict[n]=self.Fibonacci(n-1)+self.Fibonacci(n-2)
            else:
                pass
            return self.dict[n]