Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1.Copy the code

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Example 1:

Input: n = 2 Output: 1Copy the code

Example 2:

Input: n = 5 Output: 5Copy the code

recursive

The recursive method is very simple, just write the above prompt, and then determine the termination condition.

var fib = function (n) {
    if (n < 2) return n;
    return (fib(n-1)+fib(n-2))%1000000007
};
Copy the code

However, when LeetCode is submitted, it can be found that when n=44, timeout will be displayed, because there are a lot of repeated calculations in this algorithm, resulting in huge time complexity. So we need to improve, let’s save the number that we have already calculated, so that the next time we encounter the same number, we can just extract it and calculate it, and we don’t need to calculate it again.

var fib = function (n) {
    let arr = new Array(n + 1);
    return help(n)
    function help(n) {
        if (n < 2) return n;
        if (arr[n]) return arr[n];
        let num = (help(n - 1) + help(n - 2)) % 1000000007
        arr[n] = num;
        return arr[n]
    }
};
Copy the code

All we need to do is create an ARR array of length n+1 and store the calculated numbers in the index.

The iteration

If you have recursion, you have iteration, and recursion is going forward from the last number, so if you want to use iteration, you just need to start with the first number, save the first three numbers, the first two numbers, and then you can calculate the current number.

var fib = function (n) {
    if (n < 2) return n;
    let q = 0, p = 0, s = 1;
    for (let i = 2; i <= n; i++) {
        q = p;
        p = s;
        s = (p+q)%1000000007
    }
    return s
};
Copy the code