Fibonacci

What are Fibonacci numbers

What is the Fibonacci sequence? It is a sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34……. The sum of the two numbers is the sum of the first two numbers from the third number. So why introduce it, because it can generate a lot of practical problems, and at the same time, while solving the problems, it’s a good time and space complexity review.

Introduce Fibonacci sequence of three implementation methods, output the NTH number

Method one: recursion

The Fibonacci sequence of the formula is: f [n] = f (n – 1) + f (n – 2), the initial value f [0] = 0, [1] f = 1, the target o f [n].

    int Fibonacci(int n) {
        if (n==0 || n==1) return n;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
Copy the code

This method is the most garbage method, no one. Time complexity O (2^n), space O (1); Time consuming performance is too long.

Method two: memorized search

    int Fib(int n, vector<int>& dp) {
        if (n==0 || n==1) return n;
        if(dp[n] ! = -1) return dp[n];
        return dp[n] = Fib(n-1) + Fib(n-2);
    }
    int Fibonacci(int n) {
        vector<int> dp(45, -1); // Since the answer is >=0, the initial value is -1, indicating that the calculation has not been done
        return Fib(n, dp);
    }
Copy the code

Time complexity O (n), space O (n);

Method three: dynamic programming

    int Fibonacci(int n) {
    if (n == 0 || n == 1) return n;
       int a = 0, b = 1, c;
       for (int i=2; i<=n; ++i) {
           c = a + b;
           a = b;
           b = c;
       }
       return c;
    }
Copy the code

Hey, hey, it only takes three variables, and it only takes one loop; Time complexity O (n), space O (1); The interview ask you, how do the Fibonacci sequence, you chrysanthemum a tight, directly tell the third approach, the somebody else the interviewer at the moment there is a question mark, this think you to a complexity of higher overseas, and then ask you have optimization scheme, to reflect to the interview, directly blocked the road, you shall not take out more difficult algorithm behind you?

Let’s ask another question:

A frog can jump up one step or two at a time. Find out how many ways the frog can jump up a n step (different order counts different results).

Don’t be confused. Analyze it and assume that f[I] represents the number of possible methods at the ith step. Think backwards. If I go from the NTH step to the NTH step, there are two possibilities for the next step, one is to go to the n-1 step, or the other is to go to the n-2 step. So f[n] = F [n-1] + f[n-2], if you smell something familiar, that’s Fibonacci numbers;

Here’s another topic:

Let’s imagine a little bit of space, you can walk with one rectangle, or two rectangles, that’s the smell, that’s Fibonacci;

One last thing to finish:

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

At this point I believe that you are already familiar with Fibonacci numbers, but also to think, Fibonacci directly solved the problem, then I must congratulate you on the wrong answer. Didn’t you realize that, it’s much more behind words, it can also jump in n level, so f [n] = f (n – 1) + f (n – 2) + f (n – 3] [4] n – + + f… + f [1]; Wanted to think, this seems to be recursive, but how expressed in algorithm, lu head wanted to think, f = f (n – 1] [n – 2) + f (n – 3] [4] n – + + f… + f [1], [n] = 2 f * f (n – 1) = 2 * 2 * [n – 2] = f… F = 2 ^ (n – 1) * [1].

So we end up with 2 to the n minus 1 jumps.

Have you given up your studies?