python实现青蛙跳台阶算法

问题描述：
青蛙每次跳台阶每次只能跳一个台阶或两个台阶，跳到第N个台阶总共有多少种跳法

解决方法：
可以转化为斐波那契数列的方式进行求解，假设要跳N阶台阶，那么第一步有两种跳法：
（1）跳一步，后面还有n-1个台阶需要跳；
（2）跳两步，后面还有n-2个台阶需要跳。
可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和，即f(n) = f(n-1) + f(n-2)

求解方式：
（1）递归，代码很简洁，但不推荐此方式，有大量的重复计算

def JumpSteps_digui(n):
    if n in (1, 2):
        return n
    return JumpSteps_digui(n-1)+JumpSteps_digui(n-2)

（2）从下往上计算，很简单的动态规划，时间复杂度为0（n）,通常软件中采用这种写法。

def JumpFloor_new(n):
    if n in (1, 2):
        return n
    temp1, temp2 = 1, 2
    while n > 2:
        temp = temp1 + temp2
        temp1, temp2 = temp2, temp
        n -= 1
    return temp