This is the 14th day of my participation in Gwen Challenge

Topic describes

Climb the stairs

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 leetcode-cn.com/problems/cl…

/ / sample 1Input:2Output:2Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2 阶
/ / sample 2Input:3Output:3Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3.  2Order +1 阶
Copy the code

The label

Dynamic programming

Analysis of the problem solving

1. Dynamic planning

It’s an old classic problem. Let me write the simplest way.

We know that we started on the flat, so we started from0In the first place. With short legs, we had only two ways to climb the stairs.1. 走1order2. 走2Step began to climb up and walk to the first1Steps. We have to take the first option. Take the stairs. Go to the first2Steps, we have two ways to go, two steps1Take the steps or just go2Order the steps. Go to the first3Step step, we have three ways,1+1+1or1+2or2 + 1Go to the first4Steps, we have five ways,1+1+1+1.1+1+2.1+2+1.2+1+1.2+2. . Do you see a pattern, when we get to the NTH step, let's go back and see if there are only two ways to get to the NTH step.1.The first n -1Step to the NTH step2.The first n -2If you go to the NTH step, the number of options for both of them, if you add them together, is equal to the total number of options for the NTH step. F (n) = f (n -1) + f (n -2From the first1Step step let's see1:0 + 1 = 1 
2:1 + 1 = 2
3:2 + 1 = 3
4:3 + 2 = 5If it isn't the Fibonacci sequence.0 1 1 2 3 5 8 13 21.. The sequence from the first3You start with terms that are equal to the sum of the previous two terms. Knowing that, it's easy to write code.Copy the code

Go to ！！！！！

function climbStairs(n: number) :number {
    let stepOne = 0, stepTwo = 0, result = 1
    
    for(let i =1; i<=n; i++) {
        stepOne = stepTwo
        stepTwo = result
        result = stepOne + stepTwo
    }

    return result
};
Copy the code

Another, more straightforward way to express this is to maintain an array of Fibonacci numbers.

function climbStairs(n: number) :number {
    const dp: number[] = []
    dp[0] = 1
    dp[1] = 1 

    for(let i =2; i<=n; i++) {
        dp[i] = dp[i -1] + dp[i-2]}return dp[n]
};

Copy the code

The last

From today not pigeon, every day an algorithm problem and published articles, first want to solve the problem group for Top100, the sixth topic finished work!!