一、题目
写一个函数，输入 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提示：
0 <= n <=100
注意：本题与主站 509 题相同：https://leetcode-cn.com/problems/fibonacci-number/
二、思路
1. 动态规划
这一题结合题目我们可以得出状态转移方程：
$$
dp[i]=
\begin{cases}
0& \text{n=0}\
1& \text{n=1}\
dp[i-1]+dp[i-2]& \text{1 < n <= 100}
\end{cases}
$$
在最后返回结果的时候，返回的是与1000000007取模的结果。
三、代码
1. 动态规划
class Solution:
def fib(self, n: int) -> int:
a, b = 1, 0
for _ in range(n):
a, b = b, a+b
return b % 1000000007四、表现
| method | 运行时间 | 表现 | 内存消耗 | 表现 |
|---|---|---|---|---|
| 1. 动态规划 | 36ms | 86.42% | 13.5MB | 9.16% |
