I am a junior student, MOE a new xiaobai, the first time to publish an article, there is a bad place I hope you can point out comments, younger brother is not talented, I hope to learn more things.

Without further ado, let’s get down to business.

Stair climbing algorithm

We all know that the most important thing about stair climbing algorithms is the idea of recursion, so let’s talk about recursion

What’s the recursion?

  1. concept

  • In a program a function calls itself directly or indirectly

  • Call yourself directly

  • Call yourself indirectly

  • Out of the structure, out of the results

  1. thought

  • Recursive call, or eventually to convert to their own function

  • If you have a function fd, if it’s a recursive function, at the end of the day the problem is converted to function FD

  • The idea of recursion is to turn an unknown problem into a solved one

function fd() {... fd()... }Copy the code

With recursion in mind, let’s talk about stair climbing algorithms

N steps of stairs

First, when there is only one staircase, there is obviously only one way to go; When there are two stairs, it is also obvious that there are two ways to go. You get the following statement

if (n == 1 || n == 2) {
        return n;
    }
Copy the code

So the idea of first order and second order comes out, but what about when the order is third or fourth or even n? This is where the idea of recursion comes in, if the order is n, it goes like this:

   climbStairs(n - 2) + climbStairs(n - 1);
Copy the code

Our code came out in the middle of a conversation

var climbStairs = function (n) {
    if (n == 1 || n == 2) {
        return n;
    }
    else {
        returnclimbStairs(n - 2) + climbStairs(n - 1); }}Copy the code

At this point, you can go to LeetCode and submit your code happily, and you’ll find out

????? What the hell is this? I worked so hard to type the code, and you’re doing this with me?

When I calmed down and thought about it carefully, I found the problem. It turned out to be recursive repeated calculation that led to memory overflow, and then I had to optimize the allocation of memory. Recursion can be optimized for loops, and I solved this problem by defining multiple variables to reduce memory allocation.

function climbStairs(n){
    if (n == 1 || n == 2) 
        return n;

let ret = 0,
pre = 2,
prepre = 1;
for(leti = 3; i <= n ; i++){ ret = pre + prepre; prepre = pre; pre =ret }return ret;
}
Copy the code

conclusion

When I first got the problem of climbing stairs, I immediately thought of using recursive methods to do it, and then went to inquire some knowledge about recursion. Then I analyzed the problem. It was a special case when the stairs had only one or two steps, so I wrote the complete code of n steps with recursive thought. When I went to LeetCode to submit the code, I realized the problem of memory overflow, optimized the code, and finally wrote this code.