This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

LvLin recently in the study of dynamic programming related algorithms, preach a simple dynamic programming introductory topic, I hope to give you inspiration.

Fibonacci numbers

Fibonacci numbers are familiar to all of you. The 0th term of the sequence is 0, the first term is 1, and each subsequent term is the sum of the first two, which can be expressed as follows:

F (0) = 0, F (1) = 1, F (n) = F (n - 1) + F (n - 2), n > 1Copy the code

Easy to understand, right? So if you write a function that returns the corresponding Fibonacci number based on the argument n, how do you do that?

It is also very simple, according to the above formula, in a recursive way, as shown below

var fib = function(n) {
    if (n <= 1) {
        return n;
    }

    return fib(n-1) + fib(n-2);
};
Copy the code

So if n is 8, we have to compute fib of 7 and fib of 6, and when we run fib of 7, we have to compute fib of 6 and fib of 5, and we can see that fib of 6 is computed twice.

Let’s use a tree to represent the recursion:

You can see that there are a lot of duplicate numbers being counted. Is there any way to optimize it?

If we save all the figures that have been calculated, can we avoid double counting? The reference code is shown below:

var fib = function(n) {
    let arr = new Array(n+1); // Don't forget 0
    arr[0] = 0;
    arr[1] = 1;

    function fibonacci(i) {
        if (arr[i] == undefined) {
            arr[i] = fibonacci(i-1) + fibonacci(i-2)}return arr[i];
    };

    return fibonacci(n);
};
Copy the code

Let’s see what the optimized recursion tree looks like:

The optimization effect is very obvious.

Let’s take 8 again. Since we can start at 8 and recurse from the top down to 0, can’t we just start at 0 and work from the bottom up to 8? The code is as follows:

var fib = function(n) {
    let arr = new Array(n+1); // Don't forget 0
    arr[0] = 0;
    arr[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }

    return arr[n];
};
Copy the code

Have you learned? So let’s see if we can do this in LeetCode.

And by the time you see this, you’ve got a basic dynamic programming algorithm. The so-called dynamic programming is actually the idea of solving the next step based on the current solution by remembering the already solved solution.

We’ve just recorded the solutions we’ve solved in an array called DP table, or memo. By arr[I] = arr[i-1] + arr[i-2] constantly find the next solution, this is the method of solving the next step based on the current solution.

There’s room for further refinement on this problem. Can you think about how to further optimize the space?

The relevant code is as follows:

var fib = function(n) {
    if (n < 2) return n;

    let a = 0, b = 0, c = 1;
    for (let i = 2; i <= n; i++) {
        a = b;
        b = c;
        c = a+b;
    }

    return c;
};
Copy the code

Understand? Can you try this problem again?

If this article gave you something to think about, give LvLin a thumbs up