LeetCode之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步。

每一次你都可以爬一步或者爬两步，问有多少种方式爬到楼顶？

【分析】

设 f (n) 表示爬 n 阶楼梯的不同方法数，为了爬到第 n 阶楼梯，有两个选择：
从第 n - 1 阶前进 1 步；
从第 n - 2 阶前进 2 步；
因此，有 f (n) = f (n 1) + f (n 2)。
这是一个斐波那契数列。

【代码1】

// 递归
class Solution {
public:
    int climbStairs(int n) {
        return Fibonacci(n);
    }
private:
    int Fibonacci(int n){
        if(n <= 2){
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

【代码2】

/*********************************
*   日期：2014-01-23
*   作者：SJF0115
*   题号: Climbing Stairs
*   来源：http://oj.leetcode.com/problems/climbing-stairs/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; // 迭代，时间复杂度 O(n)，空间复杂度 O(1) class Solution { public: int climbStairs(int n) { int prev = 0; int cur = 1; for(int i = 1; i <= n ; ++i){ int tmp = cur; cur = prev + cur; prev = tmp; } return cur; } }; int main() { Solution solution; int result; result = solution.climbStairs(40); printf("Result:%d\n",result); return 0; } 
    
   
  

【代码3】

/*********************************
*   日期：2014-01-23
*   作者：SJF0115
*   题号: Climbing Stairs
*   来源：http://oj.leetcode.com/problems/climbing-stairs/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; // 数学公式，时间复杂度 O(1)，空间复杂度 O(1) class Solution { public: int climbStairs(int n) { double s = sqrt(5); return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5); } }; int main() { Solution solution; int result; result = solution.climbStairs(40); printf("Result:%d\n",result); return 0; }