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

标签：记忆化搜索、数学、动态规划
难度：简单

题目大意 #

给定一个整数 n。

要求：计算斐波那契数列的第 n 项。

注意：答案需对 1000000007 进行取余操作。

解题思路 #

斐波那契的递推公式为：F(n) = F(n-1) + F(n-2)。

直接根据递推公式求解即可。注意答案需要取余。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        f1 = 0
        f2 = 0
        f3 = 1
        for i in range(2, n + 1):
            f1, f2 = f2, f3
            f3 = (f1 + f2) % 1000000007
        return f3