Difficulty is simple

70. Climb the stairs

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.

The sample1Input:2Output:2Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2Order sample2Input:3Output:3Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3.  2Order +1 阶

Copy the code

My answer key

There are many ways to do it, but I think this is the best way to understand it.

var climbStairs = function(n) {
    let dp=[];  // Create an empty array with index representing the number of steps. There are several ways to climb that step
    dp[1] =1;  // There is one way to get to level 1.
    dp[2] =2;  // There are two ways to get to level 2 (1-1, 1, 2)
    for(let i=3; i<n+1; i++){// set the initial value of I to be 3, since 1,2 is known, and the loop stops at n
        dp[i]=dp[i-1]+dp[i-2]  // The way to the i-th step is the sum of the ways to the i-1 and i-2 steps
    }
    return dp[n]  // return the number of methods for the NTH step
};
Copy the code

The illustration

(It’s actually a Fibonacci sequence.)