1007- stair climbing

The title is as follows

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

Example 1：
Input ：n = 2
Output ：2
explain ： There are two ways to climb to the top .

1. 1 rank + 1 rank
2. 2 rank

Example 2：
Input ：n = 3
Output ：3
explain ： There are three ways to climb to the top .

1. 1 rank + 1 rank + 1 rank
2. 1 rank + 2 rank
3. 2 rank + 1 rank

Their thinking

Dynamic programming
Ideas and algorithms

We use it f(x) It means to climb to the first x Number of schemes for steps , Consider that the last step may have taken a step , Or maybe two steps , So we can list the following formula ：
f(x)=f(x−1)+f(x−2)

It means climbing to the third x The number of steps is to climb to the x−1 The number of steps and climbing to No x−2 The sum of the number of steps . Well understood. , Because you can only climb every time 1 Grade or 2 level , therefore f(x) Only from f(x−1) and f(x−2) Turn around , Here we need to count the total number of schemes , We need to sum these two contributions .

These are the transfer equations of dynamic programming , Let's discuss the boundary conditions . We're starting from 0 I started climbing , So from the first 0 Climb to the third level 0 We can see that there is only one solution , namely f(0)=1; From 0 Up to 1 There is only one solution at level , That is, climb one level ,f(1)=1. These two conditions can be used as boundary conditions to deduce the second n Correct results for level . We might as well write a few to verify , According to the transfer equation f(2)=2,f(3)=3,f(4)=5,……, Let's enumerate all these situations , It is found that the calculation result is correct .

It is not difficult for us to give a conclusion that both the time complexity and the space complexity are O(n) The implementation of the , But because of f(x) And the only f(x−1) And f(x−2) of , So we can use 「 The idea of scrolling arrays 」 Optimize the space complexity to O(1). This implementation is shown in the following code .

Solution code

class Solution 
{
    
public:
    int climbStairs(int n) 
    {
    
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) 
        {
    
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

Complexity analysis

Time complexity ： Loop execution n Time , Each time it takes a constant time cost , Therefore, the asymptotic time complexity is O(n).
Spatial complexity ： Only constant variables are used as auxiliary space , So the asymptotic space complexity is O(1).