《剑指offer》之Python青蛙变态跳台阶

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

1、当n=1的时候，跳法为1,记为f(1)
2、当n=2的时候，跳法为2，记为f(2)（可看作为f(2)=1+f(1)）
3、当n=3的时候，跳法为4，记为f(3)（可看作为f(3)=1+f(2)+f(1)）
4、当n=4的时候，跳法为8，记为f(4)（可看作为f(4)=1+f(3)+f(2)+f(1)）
5、当n=5的时候，跳法为16，记为f(5)（可看作为f(5)=1+f(4)+f(3)+f(2)+f(1)）
......
当第n级台阶时，此时跳法f(n) = f(n-1)+f(n-2)+......+f(1)
f(n) = f(n - 1) + ...... + f(1)
f(n - 1) = f(n - 2) + ...... + f(1)
上面两个式子相减可得：f(n) = 2f(n-1)

代码实现参考：

class Solution:
    def jumpFloorII(self,number):
        if number < 2:
            return number
        sum = 1
        while number > 1:
            sum += self.jumpFloorII(number - 1)
            number -= 1
        return sum
solu = Solution()
print('变态跳台阶跳法=',solu.jumpFloorII(3))

class Solution:
    def JumpFloorII(self,number):
        if number < 2:
            return number
        sum = 1
        for i in range(2,number + 1):
            print('sum==',sum)
            sum = 2 * sum
        return sum

solu = Solution()
print('变态跳台阶跳法==',solu.JumpFloorII(5))

打印结果参考：

sum== 1
sum== 2
sum== 4
sum== 8
变态跳台阶跳法== 16