首页 > 代码库 > leetcode 70

leetcode 70

70. Climbing Stairs

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种走法;

当n=2时,有2种走法;

当n=3时,有3种走法;

当n=4时,有5种走法;

......

当n=k时,有你n[k-1] + n[k-2]种走法;

 

代码如下:

 1 class Solution { 2 public: 3     int climbStairs(int n) { 4         if(n == 1) 5         { 6             return 1; 7         } 8         if(n == 2) 9         {10             return 2;11         }12         int a = 1;13         int b = 2;14         int c;15         for(int i = 2; i < n; i++)16         {17             c = a + b;18             a = b;19             b = c;20         }21         return c;22     }23 };

 

leetcode 70