Topic describes

Leetcode link: leetcode-cn.com/problems/fi…

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. That is:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2), where n > 1 gives you n, please calculate F(n).

Thinking to describe

It’s a classic problem in algorithms. I think of two solutions, namely recursion and dynamic programming.

The recursive method

The condition of recursion is obviously satisfied, there is a call to the function itself within the function, and there is a termination condition at the end. Advantages less code, easy to understand, but low efficiency.

Dynamic programming

Recursion is inefficient because the same function is recalculated several times. Instead of solving overlapping subproblems over and over again, dynamic programming rules suggest solving each smaller subproblem only once and recording the results in a table. Bottom-up: Obtains a larger value from a smaller value, and stores the calculated value to avoid repeated operation. High efficiency. But it takes up a little bit more space because you’re going to store the computed values.

AC code

Recursive method:

/ * * *@param {number} n
 * @return {number}* /
var fib = function(n) {
    if(n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return fib(n-1) + fib(n-2)};Copy the code

Dynamic programming:

/ * * *@param {number} n
 * @return {number}* /
var fib = function(n) {
    if(n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    let a = 2;
    let tempA = 0;
    let tempB = 1;
    while(a ! == n+1) {
        const temp = tempA + tempB;
        tempA = tempB;
        tempB = temp;
        a++;
    }
    return tempB;
};
Copy the code

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign