Fibonacci number

Any term in the Fibonacci sequence can be called a Fibonacci number. The Fibonacci sequence refers to the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...... The first and second terms of the sequence have values of 0 and 1, respectively. The value of each successive term is the sum of the first two terms. The boundary conditions of Fibonacci numbers are: F(0)=0,F(1)=1; The recurrence relation is: F(n)=F(n-1)+F(n-2);Copy the code

recursive

When we know that a problem has a recursive relationship and there are boundary conditions (exits), we can solve the problem recursivelyCopy the code

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

Recursion is the easiest way to do it, but it's also the longest, so from O(2^(n/2)) to O(2^n) we can use tail recursion to reduce the time, up to O(n).Copy the code

    function fib(first, second, n) {
        if (n < 2) return n;
        if (n === 2) return first + second;
        return fib(second, first + second, n - 1);
    }
    fib(0.1, n);
Copy the code

Dynamic programming

To be honest, dynamic programming, it's still not clear how to apply it. Although sometimes when you talk about problems, because you've done this problem or you've seen how to solve it, you know it should be solved using dynamic programming. But when I dig deeper, I always feel that because I have seen this problem with dynamic programming solution and use dynamic programming; I'm not going to do dynamic programming because I understand the idea of dynamic programming. . Alas, I digressCopy the code

The basic equation of dynamic programming has three conditions

MAX_NUM<n+1> = (X<n+1> > MAX_NUM<n>)? X<n+1> : MAX_NUM<n> This is a state transition equation, recursive relation. MAX_NUM<n> (X<n+1> > MAX_NUM<n>) X<n+1> : MAX_NUM<n>Copy the code

Using the idea of dynamic programming solution

    function fib(n) {
        / / known values
        if (n < 2) return n;
        // boundary condition F(0) = 0; F(1) = 1;
        let first = 0, second = 1, result = null;
        // State transition: The sum of the first two values equals the third
        for(let i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        };
        return result;
    }
Copy the code

Complaints too sheng intestines broken, long should look at the amount of scenery. 🏝 🏝 🏝Copy the code