[剑指Offer]变态跳台阶

题目描述

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

解题思路

1. 递归法。和跳台阶的思路一样，但是如果台阶数较多的话浪费资源是极高的。
2. 公式法。简单分析一下问题，即可得出精确解。 $$\begin{align} f(n)&=1+f(n-1)+f(n-2)+\cdots +f(2)+f(1) \\ f(n-1)&=1+f(n-2)+\cdots +f(2)+f(1) \end{align}$$ 上式中1为一次性跳上去的跳法。两式相减可得：$f(n)=2f(n-1)$，即多一层台阶，跳法翻倍。而$f(1)=1$，$f(2)=2$，故$f(n)=2^{n-1}$

代码

Python(2.7.3)

递归法

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number < 0:
            return
        elif number < 3:
            return number
        else:
            res = 1
            while number > 0:
                number -= 1
                res += self.jumpFloorII(number)
            return res

运行时间：160ms
占用内存：5856k

公式法

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number < 0:
            return
        elif number == 0:
            return 0
        else:
            return pow(2, number - 1)

运行时间：28ms
占用内存：5728k