【题目】
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;
}