Climbing Stairs（斐波那契数列问题）
最后更新于：2022-04-01 22:55:49
## 一.题目描述
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
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
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)，而网上更有博文写出了七种解斐波那契序列的方法，还要继续深入研究啊。
';