剑指offer：青蛙跳台阶

一、问题描述

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

二、问题分析

假设现在已经跳到了第 n 个台阶，那么前一步可以从哪些台阶到达呢？

如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]

如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]

。。。

如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]

那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0],在这里就可以递归了，但是也可以写成如下形式：

              | 1       ,(n=0 ) 

f(n) =     | 1       ,(n=1 )

              | 2*f(n-1),(n>=2)

三、python代码实现：

class Solution:
    def jumpFloorII(self, number):
        if number == 0:
            return 1
        cnt = 0
        for i in range(number):
            cnt += self.jumpFloorII(i)
        return cnt

class Solution:
    def jumpFloorII(self, number):
        if number == 1:
            return 1
        elif number == 0:
            return 1
        cnt = 0
        for i in range(number-1):
            cnt += 2*self.jumpFloorII(i)
        return cnt