[B] [C] [D]

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

Tip:

  • 0 <= n <= 100

F(N) = F(n-1) + F(n-2)

We can just evaluate the NTH term

Note that 0<=0, so we need to make special judgment of n =0 and n = 1

The code is as follows:

Var fib = function(n) {if(n<2) return n; Const arr = [0,1], mod = 1000000007; For (let I = 2; i<=n; I++) {arr [I] = (arr [I - 1) + arr [2] I -) % mod} / / returns the value of n items return arr [n] % mod};Copy the code

Because the NTH term of the Fibonacci sequence depends only on the n-1 and n-2 terms, the above code also has an optimization point that it can use the scrolling array to store the NTH, N-1 and n-2 terms, thus achieving the effect of optimizing the spatial complexity from O(n) to O(1)

The code is as follows:

Var fib = function(n) {if(n<2) return n; const mod = 1000000007; // let num1 = 0,num2 = 1,cur; For (let I = 2; i<=n; i++){ cur = (num1+num2)%mod; num1 = num2; num2 = cur; } // return the value of the NTH term.Copy the code

At this point we have the Leetcode – finger Offer 10-I – Fibonacci sequence

If you have any questions or suggestions, please leave a comment!