preface

This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions.

The title

Suppose you’re climbing stairs. It takes 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?

Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

Answer key

When I saw this problem, I was like, isn’t it just a math problem?

So first of all, let’s analyze this algorithmic problem math problem, where we’re really just permutations and combinations of steps. Let’s draw a table with n going from 1 to 6.

n=1

They count Number of 2 steps plan
1 0 C11
General scheme: 1

n=2

They count Number of 2 steps plan
2 0 C22
1 1 C11

Overall scheme: 1 + 1 = 2

n=3

They count Number of 2 steps plan
3 0 C33
2 1 C21

Overall scheme: C33 + C21 = 1 + 2 = 3

n=4

They count Number of 2 steps plan
4 0 C44
3 1 C31
2 2 C22

Overall scheme: C44+C31+C22 = 1+ 3 + 1 = 5

n=5

They count The number of 2 plan
5 0 C55
4 1 C41
3 2 C32

Overall scheme: C55 + C41 + C32 = 1 + 4 + 3 = 8

n=6

They count Number of 2 steps plan
6 0 C66
5 1 C51
4 2 C42
3 3 C33

Overall scheme: C66 + C51 + C42 + C33 = 1 + 5 + 6 + 1 = 13

So what do you see from the summary above? I was going to do permutations and combinations, but it turns out it’s Fibonacci numbers.

Then I wrote the following code in accordance with this idea, and I was flattered:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let res;

    if (n===1) return 1;
    if (n===2) return 2;

    res = climbStairs(n-1) + climbStairs(n-2);

    return res;
};
Copy the code

Unfortunately, I ran out of time! Maybe it’s too much recursion! Then I began a variety of searches on the Internet, found the relevant solution ideas, that is, the idea of dynamic planning!

Refer to this article.

Let me just mention the idea of dynamic programming for a second, but it’s really an optimization to save time, space complexity, to save what you did last time, so you don’t have to do it again next time, and then you go to the NTH order, and the NTH order has to be n minus 1 plus N minus 2. Now let’s look at how it dynamically programmatically pushes forward in code.

AC code

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1 || n === 2) return n;

    let a = 1;
    let b = 2;
    let temp = 0;

    for(let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }

    return temp;
};
Copy the code

conclusion

This is a look thought is a mathematical algorithm problem, the result is really careless, careless, discerning people know it is a recursive idea, who can expect to timeout, involved in the idea of dynamic planning, really never touched this idea before, today is really learned.