小青蛙跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

这题其实有点像fib数列，用递归写的

递归写法

def jumpFloor(number):
    if number <= 0:
        return 0
    if number in [1,2]:
        return number
    return jumpFloor(number - 2) + jumpFloor(number - 1)

很可惜 虽然想了出来但是并没有通过。

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大

日
好吧，用递归写的那一刻我就该意识到这一点

尾递归写法

def jumpFloor(number, curr = 2, last = 1):
    if number == 0:
        return 0
    if number == 1:
        return 1
    if number == 2:    #这里是if,如果是else也会出错
        return curr    #这里是返回curr,返回2会出错
    return jumpFloor(number - 1, curr + last, curr)

尾递归我吃了好多坑，倒数第二行返回2我简直是脑抽，因为number最终肯定会变成2，那么不管怎么样输出的结果都是2；

在这个代码里，最后的出口并不是最下面的

return jumpFloor(number - 1, curr + last, curr)

而是代码上面那个判断条件

    if number == 2:    #这里是if,如果是else也会出错
        return curr    #这里是返回curr,返回2会出错

所return的是curr，而并不是靠上级领导等下属都忙完了再来添上一笔，这点和递归很不一样。

关于第三个if可以为curr，那么第二个if是否可以也改成last呢，其实无影响，因为number根本就不可能到为1的时候。

关于倒数第3行为什么不能改else，这里有个例子

def f(n):
    if n == 0:
        print(0)
    if n == 1:
        print(1)
    else:
        print(2)

if __name__ == '__main__':
    f(0)

输出结果为

0
2

这里看下来，会一顺溜的打印下来，结果就不唯一了

还有个情况

def f(n):
    if n == 1:
        return 1
    else:
        return 2
    if n == 0:   #这句他妈逼甚至都不会被管
        return 0

if __name__ == '__main__':
    print(f(0))

在Pycharm里，写标示的下面都是亮黄灯，else下面的if语句甚至不会再执行。

总结：有多个if的情况下就不要再用else

虽然编译通过了 但是还是想试试其他写法

动态规划

pass

学到我再补8