class Solution:
    fibo = [0] * 45
    def Fibonacci(self , n: int) -> int: 
        if n <= 2:
            return 1
        if Solution.fibo[n] > 0:
            return Solution.fibo[n]
        else:
            Solution.fibo[n] = self.Fibonacci(n-1) + self.Fibonacci(n-2)
            return Solution.fibo[n]

常规思路：

递归，利用一个额外的列表（Solution.fibo）存储中间结果，避免重复计算。

这样空间复杂度和时间复杂度都是 O(n)

妙解：

参考大神题解——利用动态规划。

常规思路是从上到下递归，然后从下到上回溯；动态规划是直接从下到上

class Solution:
    def Fibonacci(self , n: int) -> int: 
        a, b, c = 1, 1, 1
        for i in range(3, n+1):
            c = a + b
            a = b 
            b = c
        return c