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 <iostream>
#include <stdio.h>
#include <vector>
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 <iostream>
#include <stdio.h>
#include <math.h>
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;
}

LeetCode之Climbing Stairs

原文：http://blog.csdn.net/sunnyyoona/article/details/18701637