剑指 Offer 10- I. 斐波那契数列

class Solution:
    # 自己写的。
    # def fib(self, n: int) -> int:
    #     # 第0项是0，第1项是1
    #     f_n_2 = 0
    #     f_n_1 = 1
    #     # i是用来计数的，和n来作比较。
    #     # i为什么要命名为2？这样可以保证n为0或者1时不会进入下边的while循环。
    #     i = 2
    #     # 第n个值是多少
    #     sum_n = 0
    #     if n == 0:
    #         sum_n = 0
    #     elif n == 1:
    #         sum_n = 1
    #     while i < n+1:
    #         sum_n = f_n_2 + f_n_1
    #         f_n_2 = f_n_1
    #         f_n_1 = sum_n
    #         i += 1
    #     # 记得答案取模
    #     return sum_n % 1000000007
    # 大佬写的，也就是稍微简化一下自己写的。
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for i in range(n):
            a, b = b, a+b
        return a % 1000000007
  # 递归
  # def fib(n):
  #   if n < 3:
  #     return 1
  #   else:
  #     return fib(n-1) + fib(n-2)