This is the question of the day for LeetCode 2021-9-4: “Offer 10-I. Fibonacci sequence”

1. Topic description

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

2. Answer

This is a classic example of dynamic programming, using dynamic programming to solve the problem.

  1. dp[i]Meaning: the first part of the Fibonacci sequenceiThe number ofdp[i]
  2. 2. By definition easily obtained:dp[i] = (dp[i - 1] + dp[i - 2])
  3. Dp array initialization:dp = [0, 1]
  4. Traversal order: By definition, the current number depends on the previous two numbers, so it is traversed from front to back
  5. Pay attention to the modulus(% 1000000007).
const fib = n= > {
    const dp = [0.1];
    for (let i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    }
    return dp[n];
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”