LeetCode链接
循环 时间复杂度 O(N)class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
递归 时间复杂度 O(k^N) k = 2
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
return self.fib(n - 1) + self.fib(n - 2)
