前言：内容包括：题目，代码实现，大致思路

题目：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(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：递归法

int fib(int n)
{int *f = (int*)malloc(sizeof(int)*101);f[0]=0;f[1]=1;int i = 0;
//得到从下标为2开始的任意一个斐波那契数值，需要得到除了已经确定好的0，1外的它前面的所有数值，这些要得到的数值，下标从2开始，至n结束for(i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];f[i]%=1000000007;}return f[n];
}

大致思路：

斐波那契数列的第0项和第1项已经确定：0 1

1 malloc动态申请一块内存空间，用于存放斐波那契数列的数值

2 f[0] = 0 f[1] = 1

   n可以看作下标

   从下标为2开始的任意的一个斐波那契数值，等于它前两项斐波那契数列数值之和

代码实现2：非递归

int fib(int n)
{int a = 0;int b = 1;int c = 0;if (n == 1){return 1;}while (n >= 2){c = a + b;c %= 1000000007;a %= 1000000007;b %= 1000000007;a = b;b = c;n--;}return c;
}

大致思路：

斐波那契数列：

0 1 1 2 3 5……

1 第0项和第1项的数值是确定的，无需通过计算得到

当n>=2，即计算的是第2项及以后的斐波那契数值，则计算方法是：数值=前两项数值之和

2 以求第5个斐波那契数列为例：

   首先得到第2项：0+1=1 第一条蓝色线

   得到第3项： 1+1 = 2 第二条蓝色线

   得到第4项：1+2 = 3 第三条蓝色线

   得到第5项：2+3 = 5 第四条蓝色线

    总共需要计算四次，通项是：c=a+b，a=b，b=c，如此循环

   最终c就是结果

记得数值都要%1000000007