首页 > 代码库 > Climbing Stairs 爬楼梯问题,每次可以走1或2步,爬上n层楼梯总方法 (变相fibnacci)

Climbing Stairs 爬楼梯问题,每次可以走1或2步,爬上n层楼梯总方法 (变相fibnacci)

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

当n=1时,有1种方法,即直接走1步

当n=2时,有2方法:连续走2步,或直接走两步

对于n,设f(n)为总方法,则 f(n) = f(n-1)+f(n-2)  

ps:f(n-1)即第一次走一步的走法,

    f(n-2)即第一次走两步的走法

归回fibnacci问题解法:

 1 class Solution { 2 public: 3     int climbStairs(int n) { 4         if(n < 0) 5             return -1; 6         int res[] = {0,1}; 7         if(n<2) 8             return res[n]; 9             10         int fib1 = 0;11         int fib2 = 1;12         13         int result = 1;14         15         for(int i = 1 ; i <= n ; i++){16             result = fib1 + fib2;17             fib1 = fib2;18             fib2 = result;19         }20         21         return result;22     }23 };

 

Climbing Stairs 爬楼梯问题,每次可以走1或2步,爬上n层楼梯总方法 (变相fibnacci)