剑指 Offer 动态规划：斐波那契数列

剑指Offer-动态规划 10- I. 斐波那契数列

编写一个函数，输入参数 n，计算斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
当 N > 1 时，F(N) = F(N - 1) + F(N - 2)。
该数列以 0 和 1 起始，后续每一项均由前两项之和构成。

计算结果需对数值进行取模操作，模数为 1e9+7（即 1000000007）。例如，若初始计算结果为 1000000008，则应返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示信息：

0 <= n <= 100

方法一：递归

【提及斐波那契数列时，人们往往首先联想到递归算法的运用。

通过将相关条件转换为递归表达式fib(n-1) + fib(n-2)来实现计算；

并以n <= 1作为递归过程的终止判断条件。

 int fib(int n){

    
     if (n <= 1) {
    
     return n;
    
     }
    
     return fib(n-1) + fib(n-2);
    
 }