📝Leetcode Fibonacci numbers

“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

The title 🌵

✏ ️ leetcode-cn.com/problems/fe…

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

💡

recursive

The last number is the sum of the first two numbers, and the first thing that comes to mind is recursion

var fib = function (n) {
    if (n == 1 || n == 0) {
        return n
    }
    return fib(n - 1) + fib(n - 2)}Copy the code

Further optimization

As can be seen from the figure, the execution time is relatively late, indicating that the code still consumes more time and needs further optimization.

🔧 problem: recursion each time need to recalculate the previous 💡 idea: adopt a cache approach, using an array 'cache' to store the results of the previous calculation (dynamic planning)Copy the code

var fib = function (n) {
    / / recurrence
    let cache = []
    for (let i = 0; i <= n; i++) {
        if (i == 1 || i == 0) {
            cache[i] = i
        } else {
            cache[i] = cache[i - 1] + cache[i - 2]}}return cache[n]
}
Copy the code

Compared to the previous consumption of time, there is a significant improvement.

📝Leetcode Fibonacci numbers

The title 🌵