There are feelings, there are dry goods, wechat search xiaoxi learning algorithm focus on this different program yuan.

GitHub github.com/ animation algorithm has been included, there are a line of large factory interview high-frequency algorithm problem solution, are explained by animation, each problem solution with at least 20+ is most likely to be the most careful algorithm problem solution, clear and easy to understand.

The title

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 > 1Copy 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.

Source: LeetCode link: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcofCopy the code

The interview scene

class Solution {
    public int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        return fib(n - 1) + fib(n - 2); }}Copy the code

Go back to school

So if YOU compute fib of 6, you can see that f of 3 is repeated three times, and f of 4 is repeated twice, and you can imagine that the higher you go, the more times you’re going to repeat.

Mnemonic recursion

class Solution {
    public int fib(int n) {
        int [] arr = new int[n + 1];
        for (int i = 0; i < arr.length;i++) {
            arr[i] = -1;
        }
        return fibWithArray(n, arr);
    }
    public int fibWithArray(int n,int [] arr) {
        if (n < 2) {
            return n;
        }
        if (arr[n] == -1) {
            arr[n] = (fibWithArray(n-1, arr) + fibWithArray(n-2, arr)) % 1000000007;
        }
        return  arr[n];
    }
}
Copy the code

Small evening: So my recursion was double counting, so I just opened up an array, and I initialized the array to be -1, and when the array was -1, Arr [N] = (fibWithArray(N-1, ARR) + fibWithArray(n-2, ARR)) % 1000000007; Arr [n] is not -1, so next time it is not -1. If (arr[n] == -1) if (arr[n] == -1) if (arr[n] == -1)

So, for example, if you compute f of 5, you can see from the previous picture, in order to compute f of 5, you have to compute f of 3 twice.

Here small evening I give an example is clear at a glance. Now you only need to use arrays once.

Mnemonic recursion example

Recursive animation

Xxi: So you can see, because of the array, when calculating f(5), f(4), f(3), f(2) is only computed once, that is to say, when calculating f(n), f(1) to f(n-1) is only computed once, which greatly reduces the time of recursion.

Dynamic programming solution

Ta: Yuki, your mnemonic recursion is top-down. The “dynamic programming” approach is “bottom-up”. In effect, the problem of small data size was solved “really” first, and the problem of large data size was solved step by step.

The Fibonacci sequence is defined by recursion, and by this recursive relationship, we can know the value of any position in the Fibonacci sequence.

The key to dynamic programming is to find the transition equation, what is the transition equation? You put thef(n)I want to do a staten, this statenIs by the staten - 1And state n - 2This is called a state shift.

So it’s easy to get the state transition equation from the Fibonacci sequence: Dp [I +1] = DP [I] + DP [I −1] The initial state of the state transition equation is easy to know :dp[0] = 1 DP [1] = 1. The NTH Fibonacci sequence we want is dp[n], so according to the transition equation, the following code can be obtained:

class Solution {
    public int fib(int n) {
        if(n < 2)
            return n;
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){ dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        returndp[n]; }}Copy the code

Dynamic programming optimization

Tubule TA: Dp [I] dp[i-1] dp[i-2], sum,b,a represent dp[I] dp[i-1].

  • For example, in order to calculate DP [3], it is necessary to calculate firstdp[2] = dp[1] + dp[0]. We don’t use arrays, which issum = b + a. At this timesum =1 b = 1 a= 0
  • In order to calculate DP [3], it is necessary to retain the calculation result of DP [2], which is sum.
  • So we leta = b = 1That is, the result of leaving A to retain dp[1]b = sum = 1That is, the result of leaving B to retain dp[2]
  • So dp[3] = b + a = 2

Let me give you a few examples.

Let’s animate it

The complexity of the

Because we don’t use arrays, it’s O(1) in space and O(n) in time.

Java solution

class Solution {
    public int fib(int n) {
        int a = 0;
        int b = 1;
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int i = 2;
        int sum=0;
        while(i <= n)
        {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
            i++;
        }
        returnsum; }}Copy the code

C + + solution

class Solution {
public:
    int fib(int n) {
        int a = 0;
        int b = 1;
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int i = 2;
        int sum=0;
        while(i <= n)
        {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
            i++;
        }
        returnsum; }};Copy the code

JS solution

/ * * *@param {number} n
 * @return {number}* /
var fib = function(n) {
    var a = 0;
    var b = 1;
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    var i = 2;
    var sum=0;
    while(i <= n)
    {
        sum = (a + b) % 1000000007;
        a = b % 1000000007;
        b = sum;
        i++;
    }
    return sum;
};
Copy the code

PY solution

class Solution(object) :
    def fib(self, n) :
        a = 0;
        b = 1;
        if(n == 0) :return 0;
        if(n == 1) :return 1;
        i = 2;
        sum=0;
        while(i <= n):
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
            i += 1;
        return sum;

Copy the code

PHP solution

class Solution {

    / * * *@param Integer $n
     * @return Integer
     */
    function fib($n) {
        $a = 0;
        $b = 1;
        if($n= =0)
            return 0;
        if($n= =1)
            return 1;
        $i = 2;
        $sum=0;
        while($i< =$n)
        {
            $sum = ($a + $b) % 1000000007;
            $a = $b;
            $b = $sum;
            $i+ +; }return $sum; }}Copy the code

The GO method

func fib(N int) int {
    a := 0;
    b := 1;
    if N == 0 {
        return 0;
    }
    if N == 1 {
        return 1;
    }
    sum := 0;
    for i := 2; i <= N; i++ {
        sum = (a + b) % 1000000007;
        a = b;
        b = sum;
    }
    return sum;
}
Copy the code

The last

Xiao Xi finally have words

  • Animation, comics, plus 6 programming languages (Java, C++, PHP, GO, Python, JS) explanation is very painstaking, I hope you can help forward to the circle of friends and friends around, so that xiao xi’s article can let more people see, xiao xi will be more motivated to update the article!

The last

The article continues to update, can be wechat search “xiaobi algorithm” for the first time to read, reply [666] I prepared for the first large factory interview high-frequency algorithm information, this article GitHub github.com/ animation algorithm has been included, there are animation algorithm solution is clear and easy to understand, welcome Star.