题解 | #斐波那契数列#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
# class Solution:
#     def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
#         c = [[0, 0], [0, 0]]
        
#         for i in range(2):
#             for j in range(2):
#                 for k in range(2):
#                     c[i][j] += a[i][k] * b[k][j]
        
#         return c
    
#     def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
#         res = [[1, 0], [0, 1]]
        
#         while n > 0:
#             if n & 1 == 1:
#                 res = self.multiply(res, a)
#             a = self.multiply(a, a)
#             n >>= 1

#         return res
    
#     def Fibonacci(self, n: int) -> int:
#         if n == 0:
#             return 0
        
#         a = [[1, 1], [1, 0]]
#         res = self.pow(a, n - 1)
        
#         return res[0][0]

# class Solution:
#     dic = {}

#     def Fibonacci(self, n: int) -> int:
#         if n == 1 or n == 2:
#             self.dic[n] = 1
#             return 1
#         else:
#             if n in self.dic:
#                 return self.dic[n]
#             else:
#                 x = self.Fibonacci(n - 1) + self.Fibonacci(n - 2)
#                 self.dic[n] = x
#             return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)


# class Solution:

#     def Fibonacci(self, n: int) -> int:
#         fib = [0] * (n + 1)
#         fib[1] = fib[2] = 1

#         for i in range(3, n + 1):
#             fib[i] = fib[i - 1] + fib[i - 2]
            
#         return fib[n]




class Solution:

    def Fibonacci(self, n: int) -> int:
        if n in [1, 2]:
            return 1

        a1 = 1
        a2 = 1
        cur = 0
        for _ in range(3, n + 1):
            cur = a1 + a2
            a2 = a1
            a1 = cur
            
        return cur