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
  • Idea 1This is a typical recursive problemnOrder can only ben-1Order across1Order orn-2Order across2The order reaches, thereforef(n)=f(n-1)+f(n-2).
int climbStairs(int n){
    if(n<=2) return n;
    return climbStairs(n-1)+climbStairs(n-2);
}
Copy the code

However, it timed out at n=45

  • Idea 2

The identifiers i1 and i2 represent the values of i-1 and i-2, and the values of i1 and i2 are updated after the values of I are evaluated.

int climbStairs(int n){
    if(n<=2) return n;
    int i1 = 1;
    int i2 = 2;
    int res;
    for(int i = 3; i <= n; i++) {
        res = i1+i2;
        i1 = i2;
        i2 = res;
    }
    return res;
}
Copy the code

Time complexity: O (n) Space complexity: O (1)