原题解答

本次的题目如下所示：

楼梯有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))

同样，我们可以使用递推的方法书写程序，提高代码的执行效率，避免因为函数的递归调用造成的效率低下。这里留一个思考题给大家，大家可以自己写一个这个题目的非递归的程序。