原题解答
本次的题目如下所示：
楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，走完n阶台阶共有多少种不同的走法？
输入格式：
输入楼梯的阶梯数n
输出格式：
输出不同走法的个数
输入样例：
10
输出样例：
89
这是一道非常经典的题目，我们可以先寻找一下上楼梯的规律。
题目告诉了我们，一次可以上1阶，也可以上2阶。如果楼梯只有1阶，那很明显只有1种方法；如果楼梯有2阶，我们可以先跨1阶、再跨1阶，也可以直接跨2阶，有2种方法。
当有3个台阶的时候，我们要么先上到第1阶，然后再上2阶；要么先上2阶（上2阶有2种方法），再上1阶。因此一共有3种方法。
当有4个台阶的时候，我们要么先上到第2阶，然后再上2阶；要么先上3阶，再上1阶。
……
通过以上的规律，我们可以发现以下规律：
这样，我们就可以看出，如果我们写成函数的递归，这道题就很容易做出来了。
def stair(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return stair(n-1) + stair(n-2)
n = int(input())
print(stair(n))当然，我们知道递归的代码效率比较低，如果想要提高代码的效率，我们可以使用递推的方式优化代码：
n = int(input())
a, b = 1, 2 # a, b分别代表n-2和n-1级的方法数，初始值为1阶和2阶的方法数
for i in range(1, n + 1):
if i == 1:
c = a
elif i == 2:
c = b
else:
c = a + b
a, b = b, c
print(c)本题拓展
本题考查的是递推算法和递归调用，题目难度★★★★★
本题的难度在于找到规律，如果找到规律了，程序本身并不难。楼梯问题的拓展有很多，如小马过河、密室逃脱等等，都是在楼梯问题的基础上进行深化的，它的基本思路一直保持不变，依然是先找规律，然后列出递推公式。
这里我们以密室逃脱为例子看看题目如何在原来的基础上进行改动（题目出处：蓝桥杯）：
提示信息：
有一个密室逃脱游戏，有100间密室连在一排，密室编号是从1开始连续排列一直排到100间密室，如下图：
游戏规则：
- 玩家初始位置在1号密室
- 每次玩家可以进入右边的一个密室，也可以跳过一个密室进入下个密室（如：当玩家当前在3号密室，他可以进入4号密室也可以进入5号密室）
- 有毒气的密室不能进入要避开。
编程实现：
给定三个正整数X，Y，M(X＜Y＜M≤100)，表示三个密室编号。X号密室和Y号密室有毒气泄漏，不能进入，玩家需要进入到M号密室，按照游戏规则进入M号密室有多少种路线方案。
例如：X=2，Y=4，M=7，进入M号密室有2种路线方案，分别是1->3->5->6->7和1->3->5->7路线。
输入描述：输入三个正整数X，Y，M(X<Y<M)，X和Y表示有毒气密室编号，M表示需要进入到密室编号，且三个正整数之间以英文逗号隔开
输出描述：输出进入M号密室有多少种路线方案
样例输入：2,4,7
样例输出：2
本道题如果没有两个毒气泄露的密室，那就跟楼梯问题完全相同了。同样是一次能够前进1个或2个，我们只是增加了一个条件，有毒气泄漏的两个密室不能进入。
那很明显，毒气泄漏的密室不能进入就意味着进入毒气泄漏的密室的方法为0种。因此，我们只需要在原来程序的基础上加入条件判断就可以完成这道题了。 即n == x or n == y时，返回值为0。具体代码如下：
def g(x, y, m):
if m == x or m == y:
return 0
else:
if x == 1:
return 1
elif x == 2:
return 2
else:
return g(x, y, m-1) + g(x, y, m-2)
x, y, m = map(int, input().split(','))
print(g(x, y, m))同样，我们可以使用递推的方法书写程序，提高代码的执行效率，避免因为函数的递归调用造成的效率低下。这里留一个思考题给大家，大家可以自己写一个这个题目的非递归的程序。
