## 一.题目描述 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阶或2阶楼梯，问爬到第n阶楼梯共有几种爬法-_-||。题目可以看成是，设`f(n)`表示爬到第`n` 阶楼梯的方法数，为了爬到第n阶楼梯，有以下两种选择：  • 从第`f(n-1)`阶前进`1`步；  • 从第`f(n-2)`阶前进`2`步；  则`f(n)`可写成：`f(n) = f(n-1) + f(n-2)` 题目转化为斐波那契数列的问题，关于这一内容，网上相关研究有很多，概念传送门：  [http://baike.baidu.com/link?url=c2Bmk2jBGbI46qTIA-qKmdTkYBrVYYrejAHzf8BJRwCekIL4Sbx48fFCRkeGdul0](http://baike.baidu.com/link?url=c2Bmk2jBGbI46qTIA-qKmdTkYBrVYYrejAHzf8BJRwCekIL4Sbx48fFCRkeGdul0) ## 二.题目分析 关于斐波那契序列，可以使用递归或者迭代来解决问题，该书列可写成以下递推关系：  显然，使用递推关系式反复迭代并不是最优的解法，在计算f(n)值时，需要计算f(1),f(2),…,f(n-1)的所有值，其中存在很多重复的运算，如计算f(4)=f(3)+f(2)，其中需要求解f(3)=f(2)+f(1)。若使用一个数组用于储存所有计算过的项，可以把时间复杂度降至O(n)，而空间复杂度也为O(n)。 这里为了追求时间复杂度，因此直接使用斐波那契的通项公式，该公式的推导过程如下：  ## 三.示例代码 ~~~ #include <iostream> using namespace std; class Solution { public: // 时间复杂度O(1) int climbStairs1(const int n) { const double sqrtNum = sqrt(5); return int(floor((pow((1 + sqrtNum) / 2, n + 1) - pow((1 - sqrtNum) / 2, n + 1)) / sqrtNum)); } // 时间复杂度O(n) int climbStairs2(const int n) { int current = 1; int last = 0; for (int i = 1; i <= n; i++) { int temp = current; current += last; last = temp; } return current; } }; ~~~ 简单的测试代码： ~~~ #include "ClimbingStairs.h" #include <iostream> int main() { int n; cout << "How many stairs? " << "Input: "; cin >> n; Solution s; int result1 = s.climbStairs1(n); int result2 = s.climbStairs2(n); cout << "How many ways to reach the finish line? " "Result1：" << result1 << endl; cout << "How many ways to reach the finish line? " "Result2：" << result2 << endl; system("pause"); return 0; } ~~~  ## 四.小结 其实使用通项公式也存在漏洞，因为通项公式使用浮点运算，还出现了物理书，因此不能保证结果的精度。而在《编程之美》一书中，还给出一种分治策略的解决方法。该算法可做到时间复杂度O(Log2n)，而网上更有博文写出了七种解斐波那契序列的方法，还要继续深入研究啊。