青蛙跳台阶

青蛙跳台阶是一道经典的递归问题，假设一只青蛙可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上n级台阶有多少种跳法。

我们可以用递归的方法来解决这个问题。当n等于1时，青蛙只能跳1级台阶，有1种跳法；当n等于2时，青蛙可以跳1级台阶两次或者跳2级台阶一次，有2种跳法。当n大于2时，青蛙可以从n-1级台阶跳1级台阶到达n级台阶，也可以从n-2级台阶跳2级台阶到达n级台阶，因此n级台阶的跳法数等于n-1级台阶的跳法数加上n-2级台阶的跳法数。

下面是一个简单的Python代码实现：

def jumpFloor(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        return jumpFloor(n-1) + jumpFloor(n-2)

当n比较大时，递归方法会变得非常慢，因为它重复计算了很多子问题。为了避免这种情况，我们可以采用动态规划的方式来解决这个问题。我们可以定义一个数组f，f[i]表示跳上i级台阶的跳法数。初始时，f[1]=1，f[2]=2。然后我们可以通过循环计算f[i]，最后返回f[n]即可。

下面是一个用动态规划的方法实现的Python代码：

def jumpFloor(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        f = [0]*(n+1)
        f[1] = 1
        f[2] = 2
        for i in range(3,n+1):
            f[i] = f[i-1] + f[i-2]
        return f[n]

这样做的时间复杂度是O(n)，比递归方法快得多。