A, the title
Write a function, enter n, and find the NTH term (F(n)) 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 codeThe Fibonacci sequence starts with 0 and 1, and the next Fibonacci number is the sum of the previous two numbers.
The answer should be modulo 1e9+7 (1000000007). If the initial result is 1000000008, return 1
Sample 1:
Input: n = 2 Output: 1Copy the codeExample 2:
Input: n = 5 Output: 5Copy the codeTip:
0 <= n <= 100
Second, the answer key
Fibonacci is kind of a classic problem, and it’s really easy to work it out, but let’s think about it a little bit, and talk about some of the methods that are commonly used.
1. Recursion method: set a few exit values, and then keep recursion. (Long time, easy to exceed the time limit)
2. One more memory array recursion method: on the basis of recursion, set a memory array, used to store the value has been calculated, in the recursion, if the existing value is directly in the memory array to take (compared to the method time is faster, can save some of the waste of repeated calculation).
3. The idea of dynamic programming (discuss several different logical writing methods) : 1. Use three variables a,b,sum to continuously calculate, and then loop n to get the final value. Sum goes forward with the three variables A,b, and loop n-1 to get the final value of 3. Put it all into the DP array (this saves the most time).
4. Finally, don’t forget to ask for %1000000007, careful!
3. Code (JS)
//1. Direct recursion usually exceeds the time limit
/ * * *@param {number} n
* @return {number}* /
let fib = function(n) {
if(n==0) {return 0;
}
if(n==1) {return 1;
}
return (fib(n-1)+fib(n-2)) %1000000007;
};
// 2. Use an array to store values from f(0) to f(n)
// This does not exceed the time limit but consumes a lot of memory and time
/ * * *@param {number} n
* @return {number}* /
// Create a null group of 1000 with new Array(1000).fill(0)
let a=new Array(1000).fill(0);
a[1] =1;
let fib = function(n) {
if(n==0) {return 0;
}
// return a[n] if a[n] exists
if(a[n]! =0) return a[n];
// If it does not exist, recurse
a[n] = (fib(n-1)+fib(n-2)) %1000000007;
return a[n];
};
// 3. Dynamic Programming 1
/ * * *@param {number} n
* @return {number}* /
let fib = function(n) {
let a=0,b=1,sum;
if(n==0)
return a;
if(n==1)
return b;
for(let i = 0 ; i<n-1 ; i++ )
{
sum=(a+b)%1000000007;
a=b;
b=sum
}
return sum;
};
// // 4. Dynamic programming 2
/ * * *@param {number} n
* @return {number}* /
let fib = function(n) {
let a=0,b=1,sum;
for(let i = 0 ; i<n ; i++ )
{
sum=(a+b)%1000000007;
a=b;
b=sum
}
return a;
};
// 4. Dynamic Programming 3
/ * * *@param {number} n
* @return {number}* /
let fib = function(n) {
// Use new Array() to generate an Array of the specified size
let dp= new Array(n+1);
dp[0] =0;
dp[1] =1;
for(let i = 2 ; i<=n ; i++ )
{
dp[i]=dp[i-1]+dp[i-2];
dp[i]%=1000000007;
}
return dp[n];
};
Copy the code4. Expand your thinking
Here we will discuss the difference between the 1,2 and 3 code logic of the dynamic programming idea I give to solve the problem:
Dynamic Programming 1: The code I for dynamic programming one goes through n minus one times, because it takes n minus one times to compute fib of n, and after n minus one times the answer is sum(so return sum), but it’s important to note that when we talk about n==0 and n==1, that’s where I <n minus 1 goes through n minus one times.
Dynamic programming 2: The code I of dynamic programming 2 loops n times, and it can be found that the answer is assigned to A (so return a) after n calculations. Compared with dynamic programming 1, it is more convenient to not discuss the value of n here. The disadvantage is that it loops one more time.
Dynamic programming 3: The code for dynamic programming 3 can be counted as dynamic programming by simply creating an array of size n+1(dp[0]=0,dp[1]=1) and then iterating through I n times. Dp [I]=dp[I -1]+dp[I -2] (And there’s no need to worry about the initial value, because dp[0] and DP [1] are assigned ahead of time!)
Finally must remember to %1000000007, details determine success or failure!
Source: LeetCode link: leetcode-cn.com/problems/fe…