题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例

示例 1：

输入：n = 2
输出：1

示例2：

输入：n = 5
输出：5

解答方法

方法一：动态规划

思路

• 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表 斐波那契数列第 i个数字 。
• 转移方程： dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义 f(n + 1) = f(n) + f(n - 1)；
• 初始状态： dp[0] = 0, dp[1] = 1，即初始化前两个数字；
• 返回值： dp[n] ，即斐波那契数列的第 n个数字。

代码

class Solution:
    def fib(self, n: int) -> int:
        if n<2:
            return n
        dp = [0 for _ in range(n+1)]
        dp[0] = 0
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-2] + dp[i-1]
        return dp[n] % 1000000007

时间复杂度

O(N)。我们计算了从 0 到 n 的值。

空间复杂度

O(N)。使用了数组 dp。