Graphic algorithm | LeetCode 70 stairs problem

Recently I began to work hard on the algorithm, and I met this very interesting topic, because I reviewed Fibonacci sequence from it, and through some data, I found the official website of the Chinese Academy of Sciences and read many popular science articles. Dig deep and you’ll see a lot.

In the spirit of love to share the original intention, sorting out this article to share with you, the topic itself is not what difficulty, welcome to exchange, algorithmmaster beg not spray, thank you.

Enter the theme.

70. What does LeetCode mean?

Suppose you are climbing the stairs. It takes you n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top of the building?

You can think about it.

Process analysis

In this case, we can take one step at a time, or we can take two steps at a time, so we have three ways:

• Walk at will in the whole course, such as all 1 level walk;
• In front of any walk, the last step only 1 step;
• Walk in front of any, the last step only 2 steps;

I have drawn a few pictures for you to understand, as follows:

I’m not going to go into the first one.

The second move, the penultimate move is as follows. There are two ways: step 1 and step 2:

The third move, the penultimate move, is as follows. There are also two ways: step 1 and step 2:

So this is what we’re going to do, starting at the last level and going down.

In the last step, there are two ways: step 1 and step 2. It can be understood that only step 1 or step 2 can reach the last layer.

• When the last step is 1 step, it starts from layer N-1;
• When the last step is 2 steps, it starts from the n-2 layer;

And just to understand the process, the number of moves at the NTH level is the sum of the number of moves at the n-1st level and the n-2nd level.

If that doesn’t make sense, take a look at the previous diagram.

Inductive analysis

Of course, when things come to a head, induction goes forward. We can enumerate several cases for analysis:

You can see that there’s a simple rule, that when you have n levels, the number of moves is going to be the number of moves in n-1 plus the number of moves in n-2.

Let’s call it f(n)=f(n-1)+f(n-2).

The first layer fixed 1 way; The second layer fixed 2 ways; . The number of moves in level 5 is equal to the number of moves in level 4 plus the number of moves in level 5.

After understanding the whole process, we can code much more easily:

Solution 1: cyclic accumulation calculation

The result is obtained by simple cyclic accumulation:

const climbStairs = (n = 1) = > {
    if(n <= 2) return n;
    let res = 0, n1 = 1, n2 = 2; // N1 indicates the first two terms, and n2 indicates the first one
    for(let i = 3; i<= n; i++){  // The first two items have fixed values, so the loop starts with the third item
        res = n1 + n2;
        n1 = n2;
        n2 = res;
    }
    return res;
}
Copy the code

Test the number of moves in layer 6:

climbStairs(6); / / 13
Copy the code

Solution 2: recursive calculation

If f(n)=f(n-1)+f(n-2), this method is simpler:

const climbStairs = (n = 1) = > {
    if(n <= 2) return n;
    return climbStairs(n-1) + climbStairs(n-2);
}
Copy the code

Test the number of moves in layer 6:

climbStairs(6); / / 13
Copy the code

This method is simple and easy to understand, but recursion can be time-consuming and prompt that LeetCode has exceeded the time limit.

Solution 3: Use the array feature

If f(n)=f(n-1)+f(n-2), return the last item in the array.

const climbStairs = n= > {
    let result = [1.2];
    for (let i = 2; i < n; i++) {
        result.push(result[i-1] + result[i-2]);
    }
    return result[n-1];
};
Copy the code

Solution 4: Take advantage of new JavaScript ES6 features

[a, b] = [c, d] :

const climbStairs = n= > {
    let a = b = 1;
    for (let i = 0; i < n; i++) {
        [a, b] = [b, a + b];
    }
    return a;
};
Copy the code

Of course, there are other solutions, welcome to discuss ~

Expand your knowledge: Take 1, 2, 3 steps at a time

If you add one more step, you can take 3 steps, and the last step will have the following situation:

• When the last step is 1 step, it starts from layer N-1;
• When the last step is 2 steps, it starts from the n-2 layer;
• When the last step is 3 steps, it starts from the n-3 layer;

To modify the previous solution, it is the same:

const climbStairs = (n = 1) = > {
    if(n <= 2) return n;
  	if(n == 3) return 4;
    return climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3);
}
Copy the code

Test the number of moves in layer 6:

climbStairs(6); / / 24
Copy the code

Expand your knowledge: The Fibonacci sequence

If you do not know what Fibonacci sequence is, here is a brief introduction. In addition, I recommend the Fibonacci class taught by Mr. Li Yongle.

It was first introduced by mathematician Leonardoda Fibonacci with rabbit breeding as an example, and the sequence is roughly as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…. . If we look carefully, we can see a pattern: starting with the third term, each term is equal to the sum of the first two terms.

In nature, there are many Fibonacci sequences, such as a common tree whose branches grow like this:

(Photo source)

You can see that the number of branches in each layer is 1, 2, 3, 5, 8… Line it up. Of course there are many others:

(Various pebonacci spirals in nature, images from the Web)

According to the Fibonacci sequence, the formula f(n)=f(n-1)+f(n-2) is obtained. It’s similar to what we listed earlier.

conclusion

This problem itself is not difficult, but if you do not clear the process and rules, it is easy to pit, write redundant code. This article only lists four simple implementation methods, if you have other implementation methods, welcome to discuss ~ haha.