Python面试题系列之11: 变态青蛙跳

Question

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

知识点详解

题目分析

这个题目与前一篇看起来很像。在上一题中限定了青蛙一次跳台阶的阶数，要么一阶要么两阶，我们分析最终得出是斐波那契数列。那么这道题又是什么数学模型呢？

假设台阶为n级，青蛙可以通过一次或者多次来完成跳跃。
跳一次：从起点直接跳到终点。
跳多次：从起点跳了若干步后(先到达 1 ~ n-1 级的中间任一级)再跳到n级。
所以最终青蛙的跳数可以这样表述： 跳到 1级 ~ n-1级 每级可能的方法数（再跳到n级） + 1（直接跳到n级）

即，F(n)可以表示为： F(n) = F(n-1) + F(n-2) + … + F(1) + 1

又因为 F(n-1) = F(n-2) + F(n-3) +…_F(1) + 1

进而可以转化为 F(n) = F(n-1) + F(n-1)

最终可得到 F(n) = 2F(n-1)

题目分析完了，答案也就出来了，接下来就是具体的代码。

解法一

def jumpFloorII(number):
    if number < 2:
        return number
    return 2 * jumpFloorII(number-1)

解法二

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

fII = lambda n: n if n < 2 else 2 * fII(n - 1)

解法三

其实在仔细分析后不难发现n级台阶的跳法还表示为2的(n-1)幂，所以就可以直接写成：

def jumpFloorII(number):
    return 2**(number-1)

Answer

分析过程及具体代码见上文。

后记

两个相似的青蛙跳台阶问题，得到的结果却是完全不同的。在面试过程中一定要看清题目！其实只要分析出题目所对应的数学模型，问题也就会迎刃而解😁😁
好了，以上就是本篇全部内容。

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