今日终于是刷到了传说中的数楼梯，这个题之前就听说过很多次，但一直没有亲手做过，今日一做，果然爆炸，太菜了T_T

洛谷P1255

上题目：

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。

举个栗子：

当有 4 节楼梯时，就有 1111, 112, 121, 211, 22 五种走法

这个就非常有意思，可能乍一想怎么都想不到和斐波拉契数列有关，当我们的台阶数 x x x 大于2时，我们的第一步可能走 1 个台阶或者走 2 个台阶，于是求下楼梯的方案数 f ( x ) f(x) f(x) 就分解为了两个问题，分别求解 f ( x − 1 ) f(x-1) f(x−1) 和 f ( x − 2 ) f(x-2) f(x−2) ，所以我们就得到了如下式子：

f ( x ) = f ( x − 1 ) + f ( x − 2 ) f(x) = f(x-1) + f(x-2) f(x)=f(x−1)+f(x−2)

看到式子就懂了，这就斐波那契数列鸭，时间复杂度为 O ( n ) O(n) O(n)

我们自然就能想到如下递推解法（当然也可以选择递归，但可能台阶数过大时反而会超时）：