一.题目描述
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)
题目转化为斐波那契数列的问题，关于这一内容，网上相关研究有很多，概念传送门： ?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)。
这里为了追求时间复杂度，因此直接使用斐波那契的通项公式，该公式的推导过程如下：
三.示例代码
;class Solution{public:n){const double sqrtNum = sqrt(5);return int(floor((pow((1 + sqrtNum) / 2, n + 1) – pow((1 – sqrtNum) / 2, n + 1)) / sqrtNum));}n){int current = 1;int last = 0;for (int i = 1; i <= n; i++){int temp = current;current += last;last = temp;}return current;}};
简单的测试代码：
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)，而网上更有博文写出了七种解斐波那契序列的方法，还要继续深入研究啊。
怕走崎岖路，莫想登高峰。
