[dynamic planning] 70. Climbing stairs

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 ？

Be careful ： Given  n  Is a positive integer .

 

 

Beyond the time limit method ;

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
        {
            return 1;
        }
        if(n==2)
        {
            return 2;
        }
        
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

 

At the beginning with vector Store array , The result is still a long time , Switch to f1,f2 了 ：

class Solution {
public:
    int climbStairs(int n) {
        int i,f1,f2,sum;
        if(n==1)
        {
            return 1;
        }
        if(n==2)
        {
            return 2;
        }
        f1=1;
        f2=2;
        for(i=3;i<=n;i++)
        {
            sum=f1+f2;
            f1=f2;
            f2=sum;
        }
        
        return f2;
    }
};

 

There is still room for optimization in time , Only more than 39.43% user