Python面试题系列之10: 青蛙跳台阶

Question

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

知识点详解

题目分析

这个题目，我们看到题干中青蛙在跳台阶的时候：一次跳跃要么1阶、要么2阶，这是个前提。

有了这个限定，我们进行详细分析下：
假定第一次跳的是1阶，那么剩下的是n-1个台阶，跳法是f(n-1)
假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
通过第1/2步的假设，总的跳法则可用这种形式表示 f(n) = f(n-1) + f(n-2)
再结合实际的情况：当只有一阶的时候 f(1) = 1，当只有两阶的时候可以有 f(2) = 2
这样不难发现，最终得出的是一个斐波那契数列，有没有很惊喜😉😉😉

           | 1, (n=1)
    f(n) = | 2, (n=2)
           | f(n-1)+f(n-2) ,(n>2,n为整数)

好了，题目分析完了，接下来就是具体的代码。这里给大家提供多达四种解法。

解法一

def jumpFloor(number):
    res = [1,2]
    while len(res) <= number:
        res.append(res[-1] + res[-2])
    if number == 1:
        return 1
    else:
        return res[number-1]

解法二

定义一个装饰器，来看看利用装饰器的解法

def moo(func):
    cache = {}
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@moo
def fib(i):
    if i < 2:
        return 1
    return fib(i-1) + fib(i-2)

解法三

利用Python的解构来实现

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return b

解法四

我们还可以借助lambda函数来实现，一行代码搞定

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

Answer

这个跳台阶题目，当我们分析出它实际就是一个斐波那契数列后，问题是不是迎刃而解。
具体代码见上文。

后记

以上四种解法，大家更中意哪种解法呢？如果大家有独特的解法，欢迎大家在评论区留言分享~

这里还有一个相似的问题留给大家：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。好了，以上就是本篇全部内容。

备注：本篇首发于知识星球「人人都是Pythonista」。