This is the 18th day of my participation in the August Challenge

Fibonacci numbers

Offer 10-i. Fibonacci sequence

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

Answer key

The traditional way to do this problem is to use recursion, but too much recursion can cause stack overflow.

Dynamic programming

To solve this problem, we can use dynamic programming to save the sum of the first two numbers for direct use next time, which greatly reduces memory stress.

 / * * *@param {number} n
  * @return {number}* /
 var fib = function(n){
   let n1 = 0, n2 = 1, sum;
   for(let i = 0; i < n; i++){
     sum = (n1 + n2) % 1000000007;
     n1 = n2;
     n2 = sum;
   }
   returnn1; } orvar fib = function(n){
     let arr = new Array(n+1).fill(0);
     arr[0] = 0;
     arr[1] = 1;
   for(let i = 2; i <= n; i++){
     arr[i] = (arr[i-1] + arr[i-2]) % 1000000007;
   }
   return arr[n];
 }
Copy the code

Frog jump step problem

Sword refers to Offer 10-II. Frog jump step problem

A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps.

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

Example 1:

Input: n = 2 Output: 2Copy the code

Example 2:

Input: n = 7 Output: 21Copy the code

Example 3:

Input: n = 0 Output: 1Copy the code

Tip: 0 <= n <= 100

Answer key

  1. If the first jump is 1 step, then there are n minus 1 steps left, f of n minus 1.
  2. If the first jump is 2 steps, then n minus 2 steps are left, and the jump is F of n minus 2.
  3. The total hop method can be concluded as: F (n) = F (n-1) + F (n-2)
  4. F (0) = 1 when there are no steps, f(1) = 1 when there are only one step
  5. You can see that the final result is a Fibonacci sequence:
| 1, f (n) (n = 0) = | 1, (n = 1) | f (n - 1) + f (n - 2), (as integer n > 1, n)Copy the code

The principle is similar to Fibonacci sequence, using the idea of dynamic programming.

 / * * *@param {number} n
  * @return {number}* /
 var numWays = function(n) {
     const arr = new Array(n+1).fill(0);
     arr[0] = 1;
     arr[1] = 1;
     arr[2] = 2;
     for(let i = 3; i<=n; i++){ arr[i] = (arr[i-1] + arr[i-2]) %1000000007
     }
     return arr[n]
 };
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up