斐波那契数列

写一个函数，输入 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

注意：对最终结果取余等价与循环过程中取余

题解1：

直接递归肯定会超时，所以自下而上，以空间换时间

 1 public int fib(int n) {
 2 
 3         if(n==0) return 0;
 4         if(n==1) return 1;
 5         int[] dp=new int[n+1];
 6         dp[1]=1;
 7         for(int i=2;i<=n;i++)
 8             dp[i]=(dp[i-1]+dp[i-2])%1000000007;
 9         return dp[n];
10     }

题解2：

因为所求值只和他的前俩个状态有关,如f(4)=f(3)+f(2),所以只需要用俩个变量保存f(3),f(2)即可

1  public int fib(int n) {
2         int a = 0, b = 1, sum;
3         for(int i = 0; i < n; i++){
4             sum = (a + b) % 1000000007;
5             a = b;
6             b = sum;
7         }
8         return a;
9     }

此种方法有很多细节，如i<n return a等，都比较高明

自己按流程走一遍可以理解的更加透彻

链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof