Lc: sword finger offer 10- I. Fibonacci series

Write a function , Input n , Fibonacci, please （Fibonacci） The number of the sequence n term （ namely F(N)）. Fibonacci series is defined as follows ：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), among N > 1.
The Fibonacci series is composed of 0 and 1 Start , The Fibonacci number after that is the sum of the two numbers before .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

Example 1：

Input ：n = 2
Output ：1
Example 2：

Input ：n = 5
Output ：5

Method ： Basic methods , Pay attention to mold taking .( I passed it ten times ,o(╥﹏╥)o)

class Solution {
    public int fib(int n) {
        int a=0;
        int b=0;
        int c=1;
        if(n<2){
            return n;
        }
        else{
            for(int i=2;i<=n;i++){
                a=b;
                b=c;
                c=(a+b)%1000000007;
            }
            return c;
        }
    }
}

At the beginning, a recursion is written , As a result, the time exceeded the limit .（ Cover your face and cry ） It still needs some technical content .

class Solution {
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        else{
            return fib(n-1)+fib(n-2);
        }
    }
}